Рюкзак DP с массивом хешей

Question

Я пытаюсь сократить время и пространство, необходимые алгоритму Knapsack DP с нецелыми значениями.

http://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-Middle_Algorithm

In particular, if the [elements] are nonnegative but not integers, we could 
still use the dynamic programming algorithm by scaling and rounding (i.e. using 
fixed-point arithmetic), but if the problem requires fractional digits of 
precision to arrive at the correct answer, W will need to be scaled by 10^d, 
and the DP algorithm will require O(W * 10^d) space and O(nW * 10^d) time. 

Алгоритм ранца DP использует [п х W] матрицу, заполняя его с результатами, но некоторые столбцы не заполняются - они не соответствуют какой-либо комбинации весов объектов. Таким образом, они просто заполняются нулями в каждом ряду и просто теряют время и пространство.

Если мы использовали массив хэшей вместо матрицы, мы могли бы сократить время и пространство.

edit: 
knapsack capacity = 2 
items: [{weight:2,value:3} ] 

    [0 1 2] 
    [0 0 0] 
2: [0 0 3] 
     ^
Do we need this column? 

Substitution with hash: 
2: {0:0, 2:3} 

В Python, вставка ДИКТ имеет O (п) худший случай и O (1) "амортизируемые" линейное время.

Я что-то упустил?

Какова была бы сложность такой вариации на алгоритме DP рюкзака?

Answer 1

Что вы говорите, если я могу сказать, что счастливые случаи - случаи, когда у вас очень мало предметов, которые нужно вставлять в рюкзак с огромным объемом. В этом случае hashmap может оказаться оптимизацией, вызывающей сложность от O(W * n) до O(min(O(2^n * n), O(W * n))) (2^n - это количество комбинаций из n элементов). Однако с этой оценкой очевидно, что для не большого количества элементов O(2^n * n) будет доминировать над другой оценкой. Также обратите внимание, что пока O(W * n) имеют один и тот же класс, константа в последнем случае значительно больше (и даже больше: оценка во втором случае учитывает сложную амортизацию, а не худший случай).

Таким образом, вы получаете, что в некоторых случаях хеш-карта может оказаться лучше, но в общем случае имеет место противоположное.