Сокращение временной сложности Knapsack 0 ~ 1 при использовании алгоритма DP

Я использую алгоритм DP, т. Е. Сохраняю значения подзадачи в 2D-массиве, где одна ось

означает n элементов и других значений w от 0 до W где W – максимальное значение

емкость рюкзака. Поэтому значение T[n-1][W] является оптимальным для меня

вычислить. Я читал в других источниках, что временная сложность этого алгоритма

O(nW) . Мой quesiton был бы: возможно ли еще раз уменьшить эту сложность?

Я нашел другой ответ, который говорит о почти такой же вещи, но я не могу это понять без примера: как понять о сокращении временной сложности на 0 ~ 1 рюкзаке

Я говорю, что нам не нужно вычислять T[i][w] с малыми значениями w поскольку они не используются в оптимуме, но я не могу получить это правильно, может ли кто-нибудь дать подробный и наглядный пример? Это мне очень понравилось бы.

2D-массив, который вы пытаетесь заполнить, имеет размер n на W (на самом деле, W + 1, так как значения идут от 0..W , но по 0..W не влияет на асимптотическую сложность здесь). Поэтому, чтобы заполнить этот массив, вам нужно будет выполнить хотя бы n*W работу (даже если вы просто инициализируете массив для всех нhive!).

Следовательно, Θ (nW) (плотно связанный, который является как O (nW), так и Ω (nW)), является лучшим, что вы можете сделать в терминах асимптотической алгоритмической временной сложности.

Это то, что делает решение динамического программирования настолько classным, состоит в том, что вы тратите постоянное время на каждый элемент массива решений (в данном случае 2D), выполняющий некоторую постоянную работу, снизу вверх (это контрастирует со сложностью верхнего уровня, рекурсивное решение!).