냅색(Knapsack) 알고리즘 예제

냅색 알고리즘 두가지 예제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

/*     jw :: 보석의 무게     jp :: 보석의 가격     보석이 무한대로 있을 때 150kg 까지 가방에 담을 수 있을때 얻을 수 있는 최대 가치는? */   #include <iostream>   #define MAXW 101 #define MAXN 31 #define max(a,b)(a > b ? a : b) int dp1[MAXW];   int n; int w; int jWeight[MAXN] = { 0,2,4,7,3 }; int jPrice[MAXN] = { 0,10,40,30,50 };   void knapsack1() { // 보석이 무한대     for (int i = 1; i <= w; i++) // 가방         for (int j = 1; j <= n; j++) // 보석             if (jWeight[j] <= i) // 가방에 보석을 넣을 공간이 존재한다면                 dp1[i] = max(dp1[i], dp1[i - jWeight[j]] + jPrice[j]);  }   int dp2[MAXN][MAXW]; void knapsack2() { // 보석이 1개     for (int i = 1; i <= n; i++) // 보석         for (int j = jWeight[i]; j <= w; j++) // 가방, 어짜피 보석보다 큰가방부터 보면되니 jWeight[i]부터             dp2[i][j] = max(dp2[i - 1][j], dp2[i - 1][j - jWeight[i]] + jPrice[i]); // i - 1번보석 안넣은 값,  i - 1번 보석 넣고 값어치 더한 값으로 갱신 }   int dp3[2][MAXW]; void knapsack3() { // 보석이 1개     for (int i = 1; i <= n; i++) // 보석         for (int j = jWeight[i]; j <= w; j++) // 가방, 어짜피 보석보다 큰가방부터 보면되니 jWeight[i]부터             dp3[i & 1][j] = max(dp3[(i - 1) & 1][j], dp3[(i - 1) & 1][j - jWeight[i]] + jPrice[i]); } int main() {     n = 4;     w = 10;       knapsack1();     knapsack2();     knapsack3();       printf("max :: %d\n", dp1[w]);     printf("max :: %d\n", dp2[n][w]);     printf("max :: %d\n", dp3[n & 1][w]);     return 0; } /*     A 위에는 A     B 위에는 B 불가능 */ #include<iostream>   using namespace std;   int dp[102][2]; int main() {     dp[0][0] = dp[0][1] = 1; // A B       for (int i = 1; i <= 10; i++) {         dp[i][0] = dp[i - 1][0] + dp[i - 1][1];         dp[i][1] = dp[i - 1][0];     }     for (int i = 0; i <= 10; i++) {         cout << "i :: " << i << " dp :: " << dp[i][0] + dp[i][1] << endl;     }       return 0; }     Colored by Color Scripter

cs