动态规划之背包问题(java)全面总结
总结整理不易，如果对你有所帮助，不妨动手点个免费的赞哦，收藏关注不迷路[比心]~
1. 01背包
有一个体积为V的背包，商店有n个物品，每个物品有一个价值v和体积w，每个物品只能被拿一次，问能够装下物品的最大价值。
这里每一种物品只有两种状态即“拿”或“不拿”设状态dp[i][j]表示到第i个物品为止，拿的物品总体积为j的情况下的最大价值。
我们并不关心某个物品有没有被拿，只关心当前体积下的最大价值。
转移方程为:
dp[i][j]= max(dp[i][j],dp[i-1][j-w]+v);
如果不拿物品i，那么最大价值就是dp[i-1][j]，如果拿了就是从体积j-v转移过来，体积会变大w，价值增加v。最后输出dp[n][V];
例题：
小明的背包1
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有N 件物品，第 i 件物品的体积为 wi，价值为 vi。
小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数 w,v，表示物品的体积和价值。
1≤N≤100 ,1≤V≤1000,≤wi,vi≤10000。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 20 1 6 2 5 3 8 5 15 3 3输出
37运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 商场物品的数量
int m = sc.nextInt(); // 小明的背包容量
int[] w = new int[n]; // 用于存储物品的体积
int[] v = new int[n]; // 用于存储物品的价值
// 输入每件物品的体积和价值
for(int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
// 创建一个二维数组dp用于动态规划，dp[i][j]表示前i件物品放入容量为j的背包中所能获得的最大价值
int[][] dp = new int[n+1][m+1];
// 动态规划求解
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(j >= w[i-1]) // 如果背包容量大于等于第i件物品的体积
dp[i][j] = Math.max(dp[i-1][j-w[i-1]] + v[i-1], dp[i][j]); // 在放入第i件物品和不放入第i件物品之间选择最大价值
dp[i][j] = Math.max(dp[i-1][j], dp[i][j]); // 如果不放入第i件物品，那么背包中的价值维持不变
}
}
System.out.println(dp[n][m]); // 输出小明所能获得的最大价值
}
}
1.1 01背包优化
首先有dp[i][j] = dp[i-1][j]，相当于将dp[i-1]复制给dp[i]，然后dp[i][j]=max(dp[i][j],dp[i-1][j-w)+v)，每次j的下标都是从小的转移到大的，于是我们可以将第一维度给优化掉，直接当做一个数组，然后每次更新时，从后往前更新，这样避免了用新数据来更新新数据。即变为:dp[j]=max(dp[j],dp[j-w]+v)，dp[j]表示此时物品总重量为j的情况下的最大价值。
例题：
背包与魔法【22国赛】
题目描述
小蓝面前有 N 件物品, 其中第 i 件重量是 Wi, 价值是 Vi 。她还有一个背包, 最大承重是M。
小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?
特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 K, 同时价值翻倍。(当然小蓝也可以不使用魔法)
输入格式
第一行包含 3 个整数 N、M 和 K 。
以下 N 行, 每行两个整数Wi 和 Vi 。
输出格式
一个整数代表答案。
样例输入
3 10 3 5 10 4 9 3 8样例输出
26样例说明
选择第二件和第三件物品, 同时对第二件物品使用魔法。
评测用例规模与约定
对于 30% 的数据, 1≤N,M,K≤100.
对于 100% 的数据, 1≤N≤2000,1≤M,K≤10000,0≤Wi,Vi≤10000.
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品数量
int m = sc.nextInt(); // 背包承重上限
int k = sc.nextInt(); // 魔法增加的重量
int[] w = new int[n]; // 物品重量数组
int[] v = new int[n]; // 物品价值数组
// 输入每件物品的重量和价值
for (int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
// 创建一个二维数组dp，dp[0]表示不使用魔法时的状态，dp[1]表示使用魔法时的状态
int[][] dp = new int[2][m + 1];
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
if (j >= w[i - 1]) {
dp[0][j] = Math.max(dp[0][j - w[i - 1]] + v[i - 1], dp[0][j]);
dp[1][j] = Math.max(dp[1][j - w[i - 1]] + v[i - 1], dp[1][j]);
}
if (j >= w[i - 1] + k) {
dp[1][j] = Math.max(dp[0][j - w[i - 1] - k] + 2 * v[i - 1], dp[1][j]);
}
}
}
// 输出最大价值，选择不使用魔法和使用魔法的最大值
System.out.println(Math.max(dp[0][m], dp[1][m]));
}
}
2. 完全背包
完全背包也叫无穷背包，即每种物品有无数个的背包。
有一个体积为V的背包，商店有n个物品，每个物品有一个价值v和体积w，每个物品有无限多个，可以被拿无穷次，问能够装下物品的最大价值。
这里每一种物品只有无穷种状态即“拿0个、1个、2个…无穷多个”
设状态dp[i]表示拿的物品总体积为i的情况下的最大价值。
我们并不关心某个物品拿了几个，只关心当前体积下的最大价值。
转移方程为:dp[i]=max(dp[i],dp[i-w]+v)，现在就必须使用“新数据”来更新“新数据”因为新数据中包括了拿当前这个物品的状态，而当前这个物品是可以被拿无数次的。
最后输出dp[V]即可。
例题：
小明的背包2
题目描述
小明有一个容量为V的背包。
这天他去商场购物，商场一共有 N 种物品，第 i 种物品的体积为 wi，价值为 vi，每种物品都有无限多个。
小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。
第2∼N+1 行包含 22 个正整数 w,v，表示物品的体积和价值。
1≤N≤1000，1≤V≤10000，1≤wi,vi≤1000。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 20 1 6 2 5 3 8 5 15 3 3输出
120运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品数量
int m = sc.nextInt(); // 背包容量
int[] w = new int[n]; // 物品体积数组
int[] v = new int[n]; // 物品价值数组
// 输入每种物品的体积和价值
for (int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
// 创建一个一维数组dp，dp[i]表示背包容量为i时的最大价值
int[] dp = new int[m + 1];
// 动态规划求解
for (int i = 0; i < n; i++) {
for (int j = w[i]; j <= m; j++) {
dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]);
}
}
// 输出最大价值
System.out.println(dp[m]);
}
}
3. 多重背包
有一个体积为V的背包，商店有n种物品，每种物品有一个价值v和体积w，每种物品有s个，问能够装下物品的最大价值。
这里每一种物品只有s+1种状态即“拿0个、1个、2个…个”
在基础版模型中，多重背包就是将每种物品的s个摊开，变为s种不相同的物品，从而退化成01背包处理。
只需要在01背包的基础上稍加改动，对每一个物品循环更新s次即可
例题：
小明的背包3
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 种物品，第 i种物品的体积为 wi，价值为 vi，数量为 si。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 33 个正整数w,v,s，表示物品的体积和价值。
1≤N≤100，1≤V≤200，1≤wi,vi,si≤200。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
3 30 1 2 3 4 5 6 7 8 9输出
39运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品种类数
int m = sc.nextInt(); // 背包容量
int[] w = new int[n]; // 物品体积数组
int[] v = new int[n]; // 物品价值数组
int[] s = new int[n]; // 物品数量数组
// 输入每种物品的体积、价值和数量
for (int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
s[i] = sc.nextInt();
}
// 创建一个二维数组dp，dp[i][j]表示前i种物品在背包容量为j时的最大价值
int[][] dp = new int[n + 1][m + 1];
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= Math.min(s[i - 1], j / w[i - 1]); k++) {
dp[i][j] = Math.max(dp[i - 1][j - k * w[i - 1]] + k * v[i - 1], dp[i][j]);
}
}
}
// 输出最大价值
System.out.println(dp[n][m]);
}
}
3.1 二进制优化模型
多重背包基础模型的时间复杂度为O(nsV)，当s较大时，容易超时。
为了解决这个问题，我们可以在“拆分”操作时进行一些优化，我们不再是拆分成均为1个物品的组，而是每一组的物品个数为1、2、4、8…，最后剩下的单独为一组，这样一定存在一种方案来表示0~s的所有情况(想象二进制数的表示方法)
在经典模型中，一种物品将被拆分为s组，每组一个，而二进制优化模型中，一种物品将被拆分为约log2(s)组，其中每组个数为1、2、4、8…，例如s=11，将被拆为s=1+2+4+4。这样对拆分后的物品跑一遍01背包即可，时间复杂度为O(n*log(s)*V)。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品种类数
int m = sc.nextInt(); // 背包容量
List<Integer> a = new ArrayList<>(); // 拆分后的物品价值列表
List<Integer> b = new ArrayList<>(); // 拆分后的物品重量列表
int[] w = new int[n]; // 物品体积数组
int[] v = new int[n]; // 物品价值数组
int[] s = new int[n]; // 物品数量数组
// 输入每种物品的体积、价值和数量，并进行拆分
for (int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
s[i] = sc.nextInt();
for (int k = 1; k <= s[i]; k *= 2) {
a.add(v[i] * k);
b.add(w[i] * k);
s[i] -= k;
}
if (s[i] > 0) {
a.add(s[i] * v[i]);
b.add(s[i] * w[i]);
}
}
// 创建一个一维数组dp，dp[j]表示背包容量为j时的最大价值
int[] dp = new int[m + 1];
// 动态规划求解
for (int i = 0; i < a.size(); i++) {
int v1 = a.get(i);
int w1 = b.get(i);
for (int j = m; j >= w1; j--) {
dp[j] = Math.max(dp[j], dp[j - w1] + v1);
}
}
// 输出最大价值
System.out.println(dp[m]);
}
}
4. 二维费用背包模型
有一个体积为V的背包，商店有n种物品，每种物品有一个价值v、体积w、重量m，每种物品仅有1个，问能够装下物品的最大价值。
这里每一种物品只有2种状态即“拿0个、1个”，但是需要同时考虑体积和重量的限制。
只需要在01背包的基础上稍加改动，将状态转移方程修改为二维的即可，同样是倒着更新
dp[i][j]表示当前体积为i，重量为i的情况下所能拿的物品的最大价值。状态转移方程为dp[i][j]=max(dp[i][j],dp[i-w][j-m]+v);
例题：
题目描述
小蓝是一名著名的探险家，他即将踏上一场寻宝的冒险旅程。他的目标是寻找和收集各种神秘的宝物。他有一个神秘的行囊，能够装载各种物品。然而，这个行囊有一个特殊的规定：它的最大容量是 V，并且它能承受的最大重量是M。
小蓝来到一个古老的城堡，里面有 N 件神秘的宝物，每件宝物只能被取走一次。每件宝物都有其特定的体积 vi，重量 mi，和价值 wi。
面对眼前的宝物，小蓝需要做出决定：将哪些宝物放入他的行囊，使得宝物的总体积不超过行囊的容量，总重量不超过行囊能承受的最大重量，且价值总和最大。
你的任务是帮助小蓝决定应该选择哪些宝物，并输出这些宝物的最大总价值。
输入格式
第一行是三个整数 N,V,M,用空格隔开，分别表示宝物的数量、行囊的容量和行囊能承受的最大重量。
接下来的N 行，每行有三个整数 vi，mi，wi，用空格隔开，分别表示每一件宝物的体积、重量和价值。
数据范围保证：
0<N≤1000，0<V,M≤100，0<vi,mi≤100，0<wi≤1000。
输出格式
输出一个整数，表示可以装入行囊的宝物的最大总价值。
样例输入
10 50 50 10 10 60 20 20 100 30 30 120 40 40 160 50 50 200 60 60 240 70 70 280 80 80 320 90 90 360 100 100 400样例输出
220
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 M = sc.nextInt(); // 行囊承重上限
int[] v = new int[n]; // 宝物体积数组
int[] m = new int[n]; // 宝物重量数组
int[] w = new int[n]; // 宝物价值数组
// 输入每件宝物的体积、重量和价值
for (int i = 0; i < n; i++) {
v[i] = sc.nextInt();
m[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// 创建一个二维数组dp，dp[i][j]表示背包容量为i，承重为j时的最大价值
int[][] dp = new int[V + 1][M + 1];
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i - 1]; j--) {
for (int k = M; k >= m[i - 1]; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - v[i - 1]][k - m[i - 1]] + w[i - 1]);
}
}
}
// 输出最大价值
System.out.println(dp[V][M]);
}
}
5. 分组背包模型
每组物品有若干个价值v、体积w，有一个体积为V的背包，商店有n组物品，每组物品中至多选1个，问能够装下物品的最大价值。
前面已经见过这么多背包了，在这里就直接给出分组背包的定义
设状态dp[i][j]表示到第i组，体积为j的最大价值，在这里不能忽略第一维，否则可能导致状态转移错误!
状态转移方程为:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
例题：
小明的背包5
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共N 组物品，第i 组里有 si 件物品，物品的体积为 w，价值为 v，对于每一组只能购买一件物品。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。
接下来有N*组数据，对于每组数据的输入如下：
第一行输入一个整数 s，表示该组的物品个数。
接下来 s 行每行包含两个整数w,v，表示物品的体积和价值。1≤N,V≤102，1≤s≤102，1≤w,v≤103。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
3 58 2 1 4 1 6 1 4 9 2 5 5 4 5输出
20运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
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[] s = new int[n]; // 每组物品数量数组
int[][] W = new int[n][101]; // 每组物品体积数组
int[][] V = new int[n][101]; // 每组物品价值数组
// 输入每组物品的数量、体积和价值
for (int i = 0; i < n; i++) {
s[i] = sc.nextInt();
for (int j = 0; j < s[i]; j++) {
W[i][j] = sc.nextInt();
V[i][j] = sc.nextInt();
}
}
// 创建一个二维数组dp，dp[i][j]表示前i组物品，背包容量为j时的最大价值
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];
for (int k = 0; k < s[i - 1]; k++) {
if (j >= W[i - 1][k]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - W[i - 1][k]] + V[i - 1][k]);
}
}
}
}
// 输出最大价值
System.out.println(dp[n][V]);
}
}
版权声明：本文为博主作者：哈哈哈的懒羊羊原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_72499901/article/details/137167997
