分组背包问题

多重背包问题是简化的分组背包问题.

例题

分组背包问题-acwing

分组背包问题-acwing

状态转移分析

简单的空间压缩与 01 背包相同, 这里不再赘述.

第 i 组物品中, 可以选择任何一个物品, 也可以一个不选.

状态转移方程为:

f(i, j) = max(f(i - 1, j), f(i - 1, j - v_0) + w_0, f(i - 1, j - v_1) + w_1, ..., f(i - 1, j - v_s) + w_s).

空间压缩为:

f(j) = max(f(j), f(j - v_0) + w_0, ..., f(j - v_s) + w_s), j 从大到小遍历.

对于普通的分组背包问题, 没有普适性的优化方法.

static int[] f = new int[110];

static int[] v = new int[110];
static int[] w = new int[110];

int m, n;

// read input ...

for (int i = 1; i <= n; i++) {

    // read input to s

    for (int j = m; j >= 0; j--) {
        // read input to v[j], w[j]
    }

    for (int j = m; j >= 0; j--) {
        for (int k = 0; k < s; k++) {
            f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
        }
    }
}

System.out.println(f[m]);