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. }