Red Huang

背包の中の物品の総価値を最大にする

2. const int N = 100, W = 100000;

3. int cost[N], weight[N];

4. int c [W + 1];   // 1 つの配列だけで十分です

5. void knapsack(int n, int w)

6. {

7.     memset(c, 0, sizeof(c));

8.     for (int i = 0; i < n; ++i)

9.         for (int j = w; j - weight [i] >= 0; --j)    // 後ろから前へ

10.             c[j] = max(c[j], c[j - weight[i]] + cost[i]);

11.     cout << "最高の価値は" << c [w];

12. }