文章目录

说明:

本文所讲内容摘录自崔添翼:背包九讲,并对其中的数学内容和一些较为复杂的内容进行了删减,增加了基础的例题,只是面向初学者或者不需要深入理解背包及其衍生问题的读者,如果有能力并且有意愿加深理解,本文可能会对您形成误导,请移步崔添翼:背包九讲.

混合背包问题

混合背包问题有：

  • 01背包和完全背包混合
  • 01背包、完全背包、多重背包的混合

题目解法

只需要将问题简单的糅合在一起就可以解决问题，解决这一类问题的套路是：

  • 最外层循环i遍历物品的种类
  • 第二层循环遍j历背包的容量
    • 当物品的数量只有一个时(01背包问题)：使用01背包的转移方程
    • 当物品的数量有无限多个时(完全背包问题)：需要加一个循环遍历选择物品i的数量
    • 当物品的数量有m个时:(多重背包问题) 同完全背包问题,需要加一个循环遍历选择物品i的数量
    • 注意:以上三种条件是相互独立的,也就是三个if分支

伪代码如下:

for i ← 1 to N 
    if 第 i 件物品属于 01 背包 
        ZeroOnePack(F,Ci,Wi)
	else if 第 i 件物品属于完全背包 
        CompletePack(F,Ci,Wi)
	else if 第 i 件物品属于多重背包 
        MultiplePack(F,Ci,Wi,Ni)

01背包的转移方程

for (int i = 1; i <= N; i++) {
   
    for (int j = 0; j <= V; j++) {
   
        if (cv[i][0] <= j) {
   
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cv[i][0]] + cv[i][1]);
        } else {
   
            dp[i][j] = dp[i - 1][j];
        }
    }
}

完全背包的转移方程

for (int i = 1; i <= N; i++) {
   
    for (int j = 0; j <= V; j++) {
   
        for (int k = 0; k * cv[i][0] <= j; k++) {
   
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]);
        }
    }
}

多重背包的转移方程

for (int i = 1; i <= N; i++) {
   
    for (int j = 0; j <= V; j++) {
   
        for (int k = 0; k * cv[i][0] <= j && k <= cv[i][2]; k++) {
   
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * cv[i][0]] + k * cv[i][1]);
        }
    }
}

相关题目练习

题目URL

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

物品一共有三类：

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

每种体积是 v i v_i vi​，价值是 w i w_i wi​。

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

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v i , w i , s i v_i,w_i,s_i vi​,wi​,si​，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

  • s i = − 1 s_i=−1 si​=−1 表示第 i 种物品只能用1次；
  • s i = 0 s_i=0 si​=0 表示第 i 种物品可以用无限次；
  • s i > 0 s_i>0 si​>0 表示第 i 种物品可以使用 s i s_i si​ 次；

输出格式

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

数据范围

0 < N , V ≤ 10000 < N , V ≤ 1000 0<N,V≤10000<N,V≤1000 0<N,V≤10000<N,V≤1000
0 < v i , w i ≤ 10000 < v i , w i ≤ 1000 0<v_i,w_i≤10000<v_i,w_i≤1000 0<vi​,wi​≤10000<vi​,wi​≤1000
− 1 ≤ s i ≤ 1000 − 1 ≤ s i ≤ 1000 −1≤s_i≤1000−1≤s_i≤1000 −1≤si​≤1000−1≤si​≤1000

输入样例

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

输出样例：

8

import java.util.*;

public class Main {
   

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        // 物品的数量
        int N = sc.nextInt();
        // 背包的容量
        int V = sc.nextInt();
        // 每个物品的体积和价值
        int[][] vw = new int[N + 1][3];
        for (int i = 1; i <= N; i++) {
   
            // 体积
            vw[i][0] = sc.nextInt();
            // 价值
            vw[i][1] = sc.nextInt();
            // 数量
            vw[i][2] = sc.nextInt();
        }

        int dp[][] = new int[N + 1][V + 1];
        // 不要求完全装满背包,初始化全设置为0,因为java默认int数组为0所以象征性的初始化第一个
        dp[0][0] = 0;
        // 枚举第i件物品
        for (int i = 1; i <= N; i++) {
   
            // 枚举背包的容量j
            for (int j = 0; j <= V; j++) {
   
                // 01背包问题
                if (vw[i][2] == -1) {
   
                    if (vw[i][0] <= j) {
   
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i][0]] + vw[i][1]);
                    } else {
   
                        dp[i][j] = dp[i - 1][j];
                    }
                }// 完全背包问题 
                else if (vw[i][2] == 0) {
   
                    // 枚举选择第i种物品的数量k
                    for (int k = 0; k <= V / vw[i][0] && k * vw[i][0] <= j; k++) {
   
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * vw[i][0]] + k * vw[i][1]);
                    }
                }// 多重背包问题 
                else {
   
                    // 枚举选择第i种物品的数量k
                    for (int k = 0; k <= vw[i][2] && k * vw[i][0] <= j; k++) {
   
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * vw[i][0]] + k * vw[i][1]);
                    }
                }
            }
        }
        // 返回N件物品,背包容量为V的装入的最大价值
        System.out.println(dp[N][V]);
    }
}