《计算机算法设计与分析》P74. 0-1背包问题示例代码纠错【内附可运行完整源程序】

问题描述：给定 n 种物品和一背包。物品i的重量是 w_i，其价值为 V_i，背包的容量为 c 。问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

在选择装入背包时，对于每种物品 i 只有两种选择，即装入背包或不装入背包。不能将物品 i 装入多次，也不能只装入部分的物品 i 。因此该问题称为 0-1 背包问题。

0-1背包问题是一个特殊的整数规划问题。

#include 

using namespace std;

template
void Knapsack(Type *v, int *w, int c, int n, Type **m) {
    int jMax = min(w[n] - 1, c);    // Jmax表示装不下物品n的最大容积。例如物品n重量为5，n那么容积小于等于4的背包都装不下，价值为0
    for (int j = 0; j <= jMax; j++)
        m[n][j] = 0;    // 初始化dp数组，装不下物品n，价值为0
    for (int j = w[n]; j <= c; j++)
        m[n][j] = v[n];        // 初始化dp数组，装的下物品n，价值为v[n]
    for (int i = n - 1; i >= 1; i--) {
        jMax = min(w[i] - 1, c);// Jmax表示装不下物品i的最大容积。例如物品n重量为5，n那么容积小于等于4的背包都装不下，价值为m[i+1][j]
        for (int j = 0; j <= jMax; ++j)
            m[i][j] = m[i + 1][j];    //装不下物品i，照抄i+1的情况
        for (int j = w[i]; j <= c; j++)
            m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]); //装入物品i和不装入物品i，取最大的价值
    }
    m[1][c] = m[2][c];
    if (c >= w[1])
        m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
}

template
void Traceback(Type **m, int *w, int c, int n, int *x) {
    for (int i = 1; i < n; i++) {
        if (m[i][c] == m[i + 1][c])
            x[i] = 0;
        else {
            x[i] = 1;
            c -= w[i];
        }
        x[n] = (m[n][c]) ? 1 : 0;
    }
}

int main() {
    int n, c;
    cin >> n; // 物品个数
    cin >> c; // 背包最大容量
    int *w, *v;// 重量、价值
    w = (int *) malloc(sizeof(int) * (n + 1));
    v = (int *) malloc(sizeof(int) * (n + 1));

    int **m;
    m = (int **) malloc(sizeof(int *) * (n + 1));
    for (int i = 0; i <= n; i++)
        m[i] = (int *) malloc(sizeof(int) * (n + 1));

    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        cin >> v[i];
    }
    Knapsack(v, w, c, n, m);
    int *x;
    x = (int *) malloc(sizeof(int) * (n + 1));
    Traceback(m, w, c, n, x);
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i] == 1) {
            cout << i << " ";
            sum += v[i];
        }
    }
    cout << endl << "value:" << sum;
    return 1;
}