背包问题

发表于 | 分类于 ， |

详细可参考背包问题九讲

01背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class solution {
    public int backpack(int v, int[] c, int[] w) {
        int n = c.length;
        int w = w.length;
        int[] dp = new int[v + 1];
        for (int i = 0; i < n; i++) {
            for (int j = v; j >= 0; j--) {
                if (j >= c[i]) {
                    dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
                }
            }
        }
        return dp[v];
    }
}

如果需要把背包装满,那么需要初始化dp数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class solution {
    public int backpack(int v, int[] c, int[] w) {
        int n = c.length;
        int w = w.length;
        int[] dp = new int[v + 1];
        for (int i = 1; i <= v; i++) {
            dp[v] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < n; i++) {
            for (int j = v; j >= 0; j--) {
                if (j >= c[i]) {
                    dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
                }
            }
        }
        return dp[v];
    }
}

完全背包问题

题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class solution {
    public int backpack(int v, int[] c, int[] w) {
        int n = c.length;
        int w = w.length;
        int[] dp = new int[v + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= v; j++) {
                if (j >= c[i]) {
                    dp[j] = Math.max(dp[j - c[i]] + w[i], dp[j]);
                }
            }
        }
        return dp[v] == Integer.MIN_VALUE ? 0 : dp[v];
    }
}

多重背包

题目

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本算法

将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class solution {
    public int backpack(int v, int[] c, int[] w, int[] n) {
        int C = c.length;
        int[] dp = new int[v + 1];
        for (int i = 0; i < C; i++) {
            for (int j = v; j >= 0; j--) {
                int num = n[i];
                int power = 1;
                while (num > 0) {
                    int weight = c[i] * (power < num ? power : num);
                    num -= power;
                    power *= 2;
                    dp[j] = j >= weight ? Math.max(dp[j - weight] + w[i], dp[j]) : dp[j];
                }
            }
        }
        return dp[v];
    }
}

混合三种背包问题

题目

有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？

基本思路

1
2
3
4
5
6
7
for i=1..N
    if 第i件物品属于01背包
        for v=V..0
            f[v]=max{f[v],f[v-c[i]]+w[i]};
    else if 第i件物品属于完全背包
        for v=0..V
            f[v]=max{f[v],f[v-c[i]]+w[i]};

二维费用的背包问题

问题

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价

基本思路

状态转移方程
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

问题

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

1
2
3
4
for 所有的组k
    for v=V..0
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}