Red Huang

讓背包裡面的物品總價值最大

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

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

4. int c [W + 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. }