01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

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

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

solution

import java.util.*; public class beibao01{ 
    public static void main(String[] args){ 
    Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v = sc.nextInt(); int[] v1 = new int[n+1]; int[] w = new int[n+1]; for(int i = 1; i<=n; i++){ 
    v1[i] = sc.nextInt(); w[i] = sc.nextInt(); } // int res = helper(v1,w,n,v); int res1 = helper1(v1,w,n,v); System.out.println(res1); } private static int helper1(int[] v1, int[] w, int n, int v) { 
    int res = 0; int[] dp = new int[v+1]; for(int i=1;i<=n;i++){ 
    for(int j = v;j>=v1[i];j--){ 
    dp[j] = Math.max(dp[j],dp[j-v1[i]]+w[i]); } } return dp[v]; } public static int helper(int[] v1,int[] w, int n ,int v){ 
    int res = 0; int[][] dp = new int[n+1][v+1]; for(int i=1;i<=n;i++){ 
    for(int j = 1;j<=v;j++){ 
    dp[i][j] = dp[i-1][j]; if(j>=v1[i]){ 
    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v1[i]]+w[i]); } } } return dp[n][v]; } } 

为什么变为一维要倒叙？

为什么正好dp[n][v]为结果，

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10

solution

两个代码其实只有一句不同（注意下标）

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样

for(int i = 1 ; i<=n ;i++)
for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}

讯享网import java.util.*; public class beibaowanquan{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v = sc.nextInt(); int[] v1 = new int[n+1]; int[] w = new int[n+1]; for(int i = 1; i<=n; i++){ v1[i] = sc.nextInt(); w[i] = sc.nextInt(); } // int res = helper(v1,w,n,v); int res1 = helper1(v1,w,n,v); System.out.println(res1); } private static int helper1(int[] v1, int[] w, int n, int v) { int[] dp = new int[v+1]; for(int i=1;i<=n;i++){ for(int j = v1[i];j<=v;j++){ dp[j] = Math.max(dp[j],dp[j-v1[i]]+w[i]); } } return dp[v]; } public static int helper(int[] v1,int[] w, int n ,int v){ int res = 0; int[][] dp = new int[n+1][v+1]; for(int i=1;i<=n;i++){ for(int j = 1;j<=v;j++){ dp[i][j] = dp[i-1][j]; if(j>=v1[i]){ dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v1[i]]+w[i]); } } } return dp[n][v]; } } 

多重背包问题1

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

solution

改进完全背包

import java.util.*; public class duochong1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v = sc.nextInt(); int[] v1 = new int[n + 1]; int[] w = new int[n + 1]; int[] s = new int[n + 1]; for (int i = 1; i <= n; i++) { v1[i] = sc.nextInt(); w[i] = sc.nextInt(); s[i] = sc.nextInt(); } int res1 = helper1(v1, w, n, v, s); System.out.println(res1); } private static int helper1(int[] v1, int[] w, int n, int v, int[] s) { int[] dp = new int[v + 1]; for (int i = 1; i <= n; i++) { for (int j = v; j >= v1[i]; j--) { for (int k = 0; k <= s[i] && k * v1[i] <= j; k++) { dp[j] = Math.max(dp[j], dp[j - k * v1[i]] + k * w[i]); } } } return dp[v]; } } 

多重背包2 二进制优化

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示：
本题考查多重背包的二进制优化方法。

讯享网

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

solution

将多重背包拆成01背包，但不是一个一个拆，使用二进制拆

大神解法：

讯享网import java.util.*; public class Main{ void run(){ int n = jin.nextInt(); int m = jin.nextInt(); int p = 1; for (int i = 1; i <= n ; i++){ int V = jin.nextInt(); int W = jin.nextInt(); int S = jin.nextInt(); int k = 1; while (S > k){ v[p] = V*k; w[p] = W*k; S -= k; k *= 2; p++; } if (S > 0){ v[p] = V*S; w[p] = W*S; p ++; } } int res = dp(p, m); System.out.println(res); } 

自己写的，未通过：

import java.util.*; public class beibao02 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int v = sc.nextInt(); int maxN = ; int[] v1 = new int[maxN]; int[] w = new int[maxN]; int p = 1; for (int i = 1; i <= n; i++) { int vv = sc.nextInt(); int ww = sc.nextInt(); int s = sc.nextInt(); int k = 1; while (s > k) { v1[p] = vv * k; w[p] = ww * k; s -= k; k *= 2; p++; } if (s > 0) { v1[p] = vv * s; w[p] = ww * s; p++; } } int res1 = helper1(v1, w, n, v); System.out.println(res1); } private static int helper1(int[] v1, int[] w, int n, int v) { int[] dp = new int[v + 1]; for (int i = 1; i <= n; i++) { for (int j = v; j >= v1[i]; j--) { dp[j] = Math.max(dp[j], dp[j - v1[i]] + w[i]); } } return dp[v]; } } 

多重背包

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

数据范围
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

混合背包问题

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

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。

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

si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8

solution

讯享网import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 物品个数 int V = sc.nextInt(); // 背包总容量 int[] dp = new int[V + 1]; for(int i = 0; i < N; i++){ int v = sc.nextInt(); // 体积 int w = sc.nextInt(); // 价值 int s = sc.nextInt(); // 数量 if(s == 0){ // 完全背包问题 for(int j = v; j <= V; j++){ dp[j] = Math.max(dp[j], dp[j - v] + w); } }else{ // 多重背包问题，01背包是多重背包的特例，可以一并处理 s = Math.abs(s); for(int j = 1; s >= j; s -= j, j *= 2){ for(int k = V; k >= j * v; k--){ dp[k] = Math.max(dp[k], dp[k - j * v] + j * w); } } if(s > 0){ for(int j = V; j >= s * v; j--){ dp[j] = Math.max(dp[j], dp[j - s * v] + s * w); } } } } System.out.println(dp[V]); } } 

二维费用背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8

import java.util.Scanner; public class Main{ public static void main(String[] args) { // N个物品 int N; // 背包体积 int V; // 背包承受最大的重量 int M; // 每个物品的体积 int[] v; // 每一个物品的重量 int[] m; // 每一个物品的价值 int[] w; // start input Scanner input = new Scanner(System.in); N = input.nextInt(); V = input.nextInt(); M = input.nextInt(); v = new int[N + 1]; m = new int[N + 1]; w = new int[N + 1]; for (int i = 1; i <= N; i++) { v[i] = input.nextInt(); m[i] = input.nextInt(); w[i] = input.nextInt(); } input.close(); Main solution = new Main(); // System.out.println(solution.two_dimension_knapsack_problem_1(N,V,M,v,m,w)); System.out.println(solution.two_dimension_knapsack_problem_2(N,V,M,v,m,w)); } / * 传统解法，即没有优化的解法，这个解法对于n种约束需要构建一个n维的dp矩阵 * @param N 题目提供N个物品 * @param V 背包的总体积 * @param M 背包承受最大的重量 * @param v 每个物品的体积 v[i],长度为N+1,第0位无用 * @param m 每个物品的重量 m[i],长度为N+1,第0位无用 * @param w 每个物品的价值 w[i],长度为N+1,第0位无用 * @return 在给定物品，背包总体积以及背包最大重量的情况下，背包能装的物品的最高总价值 */ public int two_dimension_knapsack_problem_1(int N, int V, int M, int[] v, int[] m, int[] w){ int[][][] dp = new int[N+1][V+1][M+1]; for(int i = 1; i <= N; i++){ for(int j = 1; j <= V; j++){ for(int k = 1; k <= M; k++){ if(j < v[i] || k < m[i]){ // 客观条件限制，不能选择当前物品N dp[i][j][k] = dp[i-1][j][k]; }else { dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-v[i]][k-m[i]] + w[i]); } } } } return dp[N][V][M]; } / * 优化版 * @param N 题目提供N个物品 * @param V 背包的总体积 * @param M 背包承受最大的重量 * @param v 每个物品的体积 v[i],长度为N+1,第0位无用 * @param m 每个物品的重量 m[i],长度为N+1,第0位无用 * @param w 每个物品的价值 w[i],长度为N+1,第0位无用 * @return 在给定物品，背包总体积以及背包最大重量的情况下，背包能装的物品的最高总价值 */ public int two_dimension_knapsack_problem_2(int N, int V, int M, int[] v, int[] m, int[] w) { int[][] dp = new int[V+1][M+1]; for(int i = 1; i <= N; i++){ for(int j = V; j >= 1; j--){ for(int k = M; k>= 1; k--){ if(j < v[i] || k < m[i]){ // 客观条件限制，不能选择当前物品N dp[j][k] = dp[j][k]; }else { dp[j][k] = Math.max(dp[j][k], dp[j-v[i]][k-m[i]] + w[i]); } } } } return dp[V][M]; } / * 所谓的优化，就是省去了代表N的那一维，即将： * dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-v[i]][k-m[i]] + w[i]); * 优化为 * dp[j][k] = Math.max(dp[j][k], dp[j-v[i]][k-m[i]] + w[i]); * 这样整体的空间复杂度可以除以N，空间复杂度降低了；时间复杂度不变，还是三层循环 * * 优化需要对遍历的顺序做一点改变，以保证遍历的时候，拿到的数据是 真·[i-1] 时刻的，而不是被更新过了的 * 如果不修改遍历的顺序，更新矩阵数据的时候时，对于体积V和质量M ,是按照从小到大的顺序更新的， * 即，在计算dp[j][k] = Math.max(dp[j][k], dp[j-v[i]][k-m[i]] + w[i]) 时， * 本来要求dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-v[i]][k-m[i]] + w[i]) ，但是由于这里代表N的维度没有了， * 造成dp[i-1][j-v[i]][k-m[i]]被提前更新为了dp[i][j-v[i]][k-m[i]]，这样拿到的数据是错误的，最后的结果也是错误的 * （这样做的效果，实际上等于计算了一个二维约束下的完全背包问题，而不是二维约束下的01背包问题） * * 通过改变 j 和 k 的遍历顺序，保证在更新dp[j][k]时，dp[j-v[i]][k-m[i]]实际上还是dp[i-1][j-v[i]][k-m[i]]， * 即 V 上小于 v ，M 上小于 k 的值，都没有更新过，还是之前的状态（i-1的状态），达到正确缩减维度的效果 */ } 

分组背包问题

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

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

输出最大价值。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8

solution

讯享网import java.util.*; class Main { Scanner sc = new Scanner(System.in); int maxV = 105; int maxN = 105; int N, M, V; int[] dp = new int[maxV]; int[] v = new int[maxN]; int[] w = new int[maxN]; void run() { N = sc.nextInt(); V = sc.nextInt(); for (int i = 0; i < N; i++) { M = sc.nextInt(); for (int j = 0; j < M; j++) { v[j] = sc.nextInt(); w[j] = sc.nextInt(); } for (int j = V; j >= 0; j--) { for (int k = 0; k < M; k++) { if (j >= v[k]) dp[j] = Math.max(dp[j], dp[j - v[k]] + w[k]); } } } System.out.println(dp[V]); } public static void main(String[] args) { Main m = new Main(); m.run(); } } 作者：Aranne 链接：https://www.acwing.com/solution/content/15853/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。