가방 2 개를위한 백팩 알고리즘

Question

나는 2 배의 배낭이있는 배낭 알고리즘에 의사 코드를 제공하는 thread을 발견했습니다. 나는 그것을 C++로 구현하려고했지만 가정 한대로 작동하지 않는다. 다음 입력 예를 들어

#include <cstdio> 
#define MAX_W1 501 
#define MAX_W2 501 

int maximum(int a, int b, int c) { 
    int max = a>b?a:b; 
    return c>max?c:max; 
} 

int knapsack[MAX_W1][MAX_W2] = {0}; 

int main() { 
    int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost 

    scanf("%d %d %d", &n, &s1, &s2); 

    // filing knapsack 
    for (int i = 0; i < n; i++) { 
     scanf("%d %d", &gain, &weight); 

     for (int w1 = s1; w1 >= weight; w1--) { 
      for (int w2 = s2; w2 >= weight; w2--) { 
       knapsack[w1][w2] = maximum(
        knapsack[w1][w2],     // we have best option 
        knapsack[w1 - weight][w2] + gain, // put into sack one 
        knapsack[w1][w2 - weight] + gain // put into sack two 
       ); 
      } 
     } 
    } 

    int result = 0; 

    // searching for result 
    for (int i = 0; i <= s1; i++) { 
     for (int j = 0; j <= s2; j++) { 
      if (knapsack[i][j] > result) { 
       result = knapsack[i][j]; 
      } 
     } 
    } 

    printf("%d\n", result); 

    return 0; 
} 

: 여기에 코드입니다

5 4 3 
6 2 
3 2 
4 1 
2 1 
1 1 

내가 가진 출력 : 내가 먼저 가방에 (1,2 모든 항목을 취할 수 있기 때문에

13 

분명히 잘못이다 두 번째 가방에 쉰다.) 합계는 16이다. 나는 의사 코드가 잘못된 곳에 대한 설명에 감사하게 생각한다. 어떤 사람들은 입력 형식을 이해하는 문제가 있기 때문에

나는 약간의 업데이 트를 만들어 :

항목 수, 자루 하나의 용량, 자루의 용량을 다음과 같이
1. 첫 번째 라인은 3 개 개의 숫자를 포함 두
2. 나중에 각 행에 두 개의 숫자가 포함 된 n 개의 줄이 있습니다 : 이득, i ​​번째 항목의 비용.
3. 는 개체 만 두 자루에 맞게 발생하는 경우를 고려하기 때문에 자루,보다 큰 500

Answer 1

사용중인 알고리즘이 잘못 표시 될 수 없음을 가정합니다. 난 당신의 코드를 다음과 같이 변경했고 지금은 올바르게 작동 : 작동하도록 코드를 수정 여기

#include <algorithm> 

using std::max; 

int max3(int a, int b, int c) { 
    return max(a, max(b, c)); 
} 

및

for (int w1 = s1; w1 >= 0; w1--) { 
    for (int w2 = s2; w2 >= 0; w2--) { 
     if (w1 >= weight && w2 >= weight) // either sack has room 
     { 
      knapsack[w1][w2] = max3(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1 - weight][w2] + gain, // put into sack one 
       knapsack[w1][w2 - weight] + gain // put into sack two 
      ); 
     } 
     else if (w1 >= weight) // only sack one has room 
     { 
      knapsack[w1][w2] = max(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1 - weight][w2] + gain // put into sack one 
      ); 
     } 
     else if (w2 >= weight) // only sack two has room 
     { 
      knapsack[w1][w2] = max(
       knapsack[w1][w2],     // we have best option 
       knapsack[w1][w2 - weight] + gain // put into sack two 
      ); 
     } 
    } 
} 

Answer 2

입니다 : -

가

#include <cstdio> 
#define MAX_W1 501 
#define MAX_W2 501 

int maximum(int a, int b, int c) { 
    int max = a>b?a:b; 
    return c>max?c:max; 
} 

int knapsack[MAX_W1][MAX_W2] = {0}; 

int main() { 
    int n, s1, s2, gain, weight; // items, sack1, sack2, gain, cost 

    scanf("%d %d %d", &n, &s1, &s2); 

    // filing knapsack 
    for (int i = 0; i < n; i++) { 
     scanf("%d %d", &gain, &weight); 
    // need to fill up all the table cannot stop if one sack is full because item might fit in other 
     for (int w1 = s1; w1 >= 0; w1--) { 
      for (int w2 = s2; w2 >= 0; w2--) { 
       int val1=0,val2=0; 
       if(weight<=w1) 
        val1 = knapsack[w1 - weight][w2] + gain; 
       if(weight<=w2) 
        val2 = knapsack[w1][w2 - weight] + gain; 

       knapsack[w1][w2] = maximum(
        knapsack[w1][w2],     // we have best option 
        val1,    // put into sack one 
        val2    // put into sack two 
       ); 


      } 
     } 
    } 


    // No need to search for max value it always be Knapsack[s1][s2] 
    printf("%d\n", knapsack[s1][s2]); 

    return 0; 
}