해시 배열이있는 배낭 DP

Question

정수가 아닌 값으로 배낭 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. 

민주당 배낭 알고리즘

결과 그것을 채우고, A [N x 폭] 행렬을 이용하지만 충전 만나지 일부 열은 - 그들이 개체 가중치의 조합과 일치하지 않는다. 이 방법을 사용하면 각 행에 0이 채워지고 시간과 공간이 낭비됩니다.

행렬 대신 해시 배열을 사용하면 필요한 시간과 공간을 줄일 수 있습니다.

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} 

파이썬에서 dict 삽입은 O (n) 최악의 경우와 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)이 동일한 클래스 인 반면 후자의 상수는 훨씬 더 큽니다 (두 번째 경우의 추정은 최악의 경우가 아니라 상각 된 복잡도를 고려함).

따라서 해시 맵이 더 좋을 수도 있지만 일반적인 경우에는 그 반대가됩니다.