동적 프로그래밍을 사용하는 배낭

Question

동적 프로그래밍을 사용하여 배낭 문제를 해결하기위한 일반적인 알고리즘이 있습니다. 하지만 W = 750000000에서는 작동하지 않습니다. 잘못된 할당 오류가 있기 때문입니다. 어떤 아이디어를 어떻게 내 W의 가치에 대해이 문제를 해결할 수 있을까요?

int n=this->items.size(); 
std::vector<std::vector<uint64_t>> dps(this->W + 1, std::vector<uint64_t>(n + 1, 0)); 
for (int j = 1; j <= n; j++) 
    for (int k = 1; k <= this->W; k++) { 
     if (this->items[j - 1]->wts <= k) 
      dps[k][j] = std::max(dps[k][j - 1], dps[k - this->items[j - 1]->wts][j - 1] + this->items[j - 1]->cost); 
     else 
      dps[k][j] = dps[k][j - 1]; 
    } 

Answer 1

우선, 하나의 차원 만 배낭 문제를 해결할 수 있습니다. 이렇게하면 dp [W] [n] (n * W 공간)에서 dp [W] (W 공간)까지 메모리가 줄어 듭니다. 여기서 볼 수 있습니다 : 0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

그러나 dp [W] 만 사용하더라도 W는 실제로 높고 메모리가 너무 많을 수 있습니다. 항목이 큰 경우 가능한 접근법의 수를 줄이기 위해 몇 가지 접근법을 사용할 수 있습니다. 먼저, W의 모든 위치가 필요하지 않으며, 무게의 합이 존재하는 것만을 필요로한다는 것을 깨달으십시오. 예를 들어

: 항목이 차지할 수 있기 때문에, 당신의 행렬의 위치 (DP) [473]를 사용하지 않습니다

W = 500 
weights = [100, 200, 400] 

는 p = [0, 100, 200, 300, 400, 500]를 배치합니다.

이

W = 5 
weights = [1,2,4] 

또 다른 더 복잡한 예 :

W = 20 
weights = [5, 7, 8] 

이전과 동일한 방법을 사용하여, 당신은 0에서 모든 가중치를 필요가 없습니다이 문제가 때와 동일하다는 것을 쉽게 알 수있다 항목 만 차지하는 위치

p = [0, 5, 7, 5 + 7, 5 + 8, 7 + 8, 5 + 7 + 8] 
p = [0, 5, 7, 12, 13, 15, 20] 

까지 작성 및 DP에서 매트릭스를 줄일 수 있기 때문에 20, [20] DP하려면 [페이지 크기] = M [7].

Answer 2

당신은 n을 표시하지 않지만, 우리는, (1) 당신이 할당하려고 얼마나 많은 데이터를 볼 수 있습니다 가정 할 경우에도 마찬가지입니다. 그래서, 그것은 다음과 같습니다

W*64*2 // Here we don't consider overhead of the vector 

이 나옵니다 :

750000000*64*2 bits = ~11.1758Gb 

것은 내가이 다음 프로그램이 수 있도록 더 많은 공간 추측하고있다. 당신은 새로운 접근법을 취할 필요가 있습니다. 아마도 문제를 여러 블록으로 처리하려고 시도했을 것입니다. 첫 번째와 두 번째 반 seperatley를 고려한 다음 교체하십시오.