0/1 背包问题 (0/1 knapsack problem)

问题

有 n 种物品，物品 i 的体积为 v[i], 价值为 p[i]. 假定所有物品的体积和价格都大于 0, 以及背包的体积为 V.
问：选择哪些物品可使在体积不超过 V 的情况下使物品的总价值最大，并求出这个总价值， 且每种物品只能选择 0 个或 1 个

思路

mp[x][y] 表示体积不超过 y 且可选前 x 种物品的情况下的最大总价值
那么原问题可表示为 mp[n][V]

递归关系：

1. mp[0][y] = 0
2. mp[x][0] = 0
3. 当 v[x] > y 时，mp[x][y] = mp[x-1][y]
4. 当 v[x] <= y 时，mp[x][y] = max{ mp[x-1][y], p[x] + mp[x-1][y-v[x]] }

解释如下：

1. 表示体积不超过 y 且可选前 0 种物品的情况下的最大总价值，没有物品可选，所以总价值为 0
2. 表示体积不超过 0 且可选前 x 种物品的情况下的最大总价值，没有物品可选，所以总价值为 0
3. 因为 x 这件物品的体积已经超过所能允许的最大体积了，所以肯定不能放这件物品， 那么只能在前 x-1 件物品里选了
4. x 这件物品可能放入背包也可能不放入背包，所以取前两者的最大值就好了， 这样就将前两种情况都包括进来了

代码

先写个简单的版本，看看以上的递归关系是否正确，程序编写是否正确。 （只求出了最大价值，没有求选择了哪些物品）

#define max(x, y) ({                \
    __typeof__(x) _max1 = (x);      \
    __typeof__(y) _max2 = (y);      \
    (void) (&_max1 == &_max2);      \
    _max1 > _max2 ? _max1 : _max2; })

/*
 * n - 物品种类
 * kv - 背包体积
 * pv - 物品体积数组，体积数据 pv[0] - pv[n-1]
 * pp - 物品价值数组，价值数据 pp[0] - pp[n-1]
 */
int zo_knapsack_problem(int n, int kv, int *pv, int *pp)
{
    int *v = pv;
    v--;            /* pv 数组从 0 开始，我们使用 v 数组从 1 开始 */
    int *p = pp;
    p--;
    int mp[n+1][kv+1];
    int x, y;

    for (y = 0; y <= kv; y++) {
        mp[0][y] = 0;
    }
    for (x = 0; x <= n; x++) {
        mp[x][0] = 0;
    }

    for (x = 1; x <= n; x++) {
        for (y = 1; y <= kv; y++) {
            if (v[x] > y) {
                mp[x][y] = mp[x-1][y];
            } else {
                mp[x][y] = max(mp[x-1][y], p[x] + mp[x-1][y-v[x]]);
            }
        }
    }

    return mp[n][kv];
}

验证正确之后，再来写个完整版（以下代码不是全部）

struct knapsack {
    int     n;              /* 物品总的种类 */
    int     kv;             /* 背包体积 */
    int     *pv;            /* 物品体积数组，大小为 n, 数据从 pv[0] 开始 */
    int     *pp;            /* 物品价值数组，大小为 n, 数据从 pp[0] 开始 */
    int     select_num;     /* 选择的物品种类数目 */
    int     *select_what;   /* 选择了哪些物品，大小为 n */
};

#define max(x, y) ({                \
    __typeof__(x) _max1 = (x);      \
    __typeof__(y) _max2 = (y);      \
    (void) (&_max1 == &_max2);      \
    _max1 > _max2 ? _max1 : _max2; })

int zo_knapsack_problem(struct knapsack *kna)
{
    int *v = kna->pv;
    v--;            /* 数组从 0 开始，我们使用从 1 开始 */
    int *p = kna->pp;
    p--;
    int n = kna->n;
    int kv = kna->kv;
    int mp[n+1][kv+1];
    int x, y;

    for (y = 0; y <= kv; y++) {
        mp[0][y] = 0;
    }
    for (x = 0; x <= n; x++) {
        mp[x][0] = 0;
    }

    for (x = 1; x <= n; x++) {
        for (y = 1; y <= kv; y++) {
            if (v[x] > y) {
                mp[x][y] = mp[x-1][y];
            } else {
                mp[x][y] = max(mp[x-1][y], p[x] + mp[x-1][y-v[x]]);
            }
        }
    }

    /* 求出哪些物品放入了背包 */
    int num = 0;
    for (x = n, y = kv; x > 0; x--) {
        if (mp[x][y] > mp[x-1][y]) {
            kna->select_what[num] = x;
            num++;
            y = y - v[x];
        }
    }
    kna->select_num = num;

    return mp[n][kv];
}