背包问题——01—完全—多重—混合

1.01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

• 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值
1
2

• 输出格式

输出一个整数，表示最大价值。
1

• 数据范围

0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
1
2

输入样例

4 5
1 2
2 4
3 4
4 5
1
2
3
4
5

输出样例：

8
1

1.1.第一种解法

• • 定义dp[i][j] 体积为i的包 ，装前j个物品时，所装的最大价值

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int N = sc.nextInt();
            int V = sc.nextInt();
            int[] volums = new int[N];
            int[] values = new int[N];
            for (int i = 0; i < N; i++) {
                volums[i] = sc.nextInt();
                values[i] = sc.nextInt();
            }
             1.定义dp[i][j] 体积为i的包 装前j个物品的最大价值
            int[][] dp = new int[V+1][N+1];
             2.base dp[0][j]==0 ，背包容量为0，肯定为0
                    dp[V][0]==0 ，一个物品都不选  则也为0
             目标dp[V][N]
            
            3.状态转移方程
            for (int i = 1; i <= V; i++) {
                for (int j = 1; j <= N; j++) {
                    判断当前背包容量是否能装下当前商品
                    装得下
                    if(volums[j-1] <= i){
                        选择 装 & 不装 
                        dp[i][j] = Math.max(values[j-1]+dp[i-volums[j-1]][j-1] , dp[i][j-1]);
                    }
                    装不下时
                    else {
                        背包容量为i时，不选j商品
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
            System.out.println(dp[V][N]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

1.2.第二种解法

• • 定义dp[i][j] 前i个商品，在背包容量为j时 所装的最大价值值

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int N = sc.nextInt();
            int V = sc.nextInt();
            int[] volums = new int[N];
            int[] values = new int[N];
            for (int i = 0; i < N; i++) {
                volums[i] = sc.nextInt();
                values[i] = sc.nextInt();
            }
             1.定义dp[i][j] 前i个商品 在背包容量为j时 最大值
            int[][] dp = new int[N+1][V+1];
             2.base dp[0][j]==0 ，一个物品都不选  则也为0
                    dp[i][0]==0 ，一背包容量为0，肯定为0
             目标dp[N][V]

             3.状态转移方程
            for (int i = 1; i <= N; i++) {  遍历前i个商品
                for (int j = 1; j <= V; j++) { 不同容量的包裹
                     判断当前背包容量是否能装下当前商品
                     装得下
                    if(volums[i-1] <= j){
                         选择 装 & 不装                             只有前i-1个商品 容量为 j-当前商品体积时一致
                        dp[i][j] = Math.max(dp[i-1][j], values[i-1]+dp[i-1][j-volums[i-1]]);
                    }
                     装不下时
                    else {
                         跟只有前i-1个商品 保持一致
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            System.out.println(dp[N][V]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2.完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。。

• 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值
1
2

• 输出格式

输出一个整数，表示最大价值。
1

• 数据范围

0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
1
2

输入样例

4 5
1 2
2 4
3 4
4 5
1
2
3
4
5

输出样例：

10
1

2.1.第一种解法

• 定义dp[i][j] 体积为i的背包，在 前j件商品中，所能装的最大价值
• 相较于1.1解法，仅改变状态转移方程
• 变量k，表示第j件商品，所能选择数量

for (int i = 1; i <= V; i++) {
                 可选商品 依次遍历
                for (int j = 1; j <= N; j++) {
                    判断当前 商品能否放下
                    依次能选择k个j商品时
                    for (int k = 0; k * volums[j] <= i; k++) {
                        dp[i][j] = Math.max(dp[i][j], k * values[j]+dp[i - k*volums[j]][j-1]);
                    }
                }
            }
1
2
3
4
5
6
7
8
9
10

2.2.第二种解法

• dp[i][j] 在前 i 件商品中 体积为 j 的背包，所能装的最大价值
• 相较于1.2解法题，仅改变状态转移方程
• • 变量k，表示第i件商品，所能选择数量

for (int i = 1; i <= N; i++) {
                 依次遍历各种背包容量
                for (int j = 1; j <= V; j++) {
                     判断当前 商品能否放下
                     依次能选择k个j商品时
                    for (int k = 0; k * volums[i] <= j; k++) {
                        dp[i][j] = Math.max(dp[i][j], k * values[i]+dp[i-1][j-k*volums[i]]);
                    }
                }
            }
1
2
3
4
5
6
7
8
9
10

3.多重背包问题

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

• 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
1
2

• 输出格式

输出一个整数，表示最大价值。
1

• 数据范围

0 < N,V ≤100
0 < vi,wi,si ≤100
1
2

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2
1
2
3
4
5

输出样例：

10
1

3.1.解法

• 定义dp[i][j] 在前 i 件商品中 体积为 j 的背包，所能装的最大价值
• 相较于2.2解法，仅改变状态转移方程
• 限制条件：
  • 1. 第i件商品的数量k < 第i件商品所能选择最大数量
  • 2. 选择k个第i件商品时，其体积 < 背包当前容量j

 可选商品 依次遍历
 for (int i = 1; i <= N; i++) {
      依次遍历各种背包容量
     for (int j = 1; j <= V; j++) {
          依次能选择k个j商品时
         for (int k = 0; (k <= nums[i]) && (k * volums[i] <= j); k++) {
             dp[i][j] = Math.max(dp[i][j], k * values[i]+dp[i-1][j-k*volums[i]]);
         }
     }
 }
1
2
3
4
5
6
7
8
9
10

4.混合背包问题

有 N 种物品和一个容量是 V 的背包。
物品一共有三类：

• 第一类物品只能用1次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 si 次（多重背包）；

每种体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

• 输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si = −1 表示第 i 种物品只能用1次；
si = 0 表示第 i 种物品可以用无限次；
si > 0 表示第 i 种物品可以使用 si 次；
1
2
3
4
5

• 输出格式

输出一个整数，表示最大价值。
1

• 数据范围

0 < N,V ≤1000 
0 < vi,wi ≤1000
−1 ≤ si ≤1000
1
2
3

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2
1
2
3
4
5

输出样例：

8
1

4.1.解法

• 相较于3.1解法，在接受输入时，判断次数的3种情况即可

for (int i = 1; i <= N; i++) {
    volums[i] = sc.nextInt();
    values[i] = sc.nextInt();
    int temp = sc.nextInt(); 
     可以用无限次时
    if (temp==0){
        nums[i] = Integer.MAX_VALUE;
    }
     只能用一次时
    else if (temp==-1){
        nums[i] = 1;
    }
     可以用有限次时
    else {
        nums[i] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17