背包问题
2019-11-05 本文已影响0人
PC_Repair
一、01 背包问题
题目
有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。
二维动态规划：
-
最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
-
状态转移方程
//dp[i][j] 表示前 i 件物品恰放入一个容量为 j 的背包可以获取的最大值
dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + v[i]}
- 代码
public static void main(String[] args) {
int[] w = new int[]{2, 3, 4, 5}; // 商品的体积 2 3 4 5
int[] v = new int[]{3, 4, 5, 6}; // 商品的价值 3 4 5 6
int bagV = 8; // 背包大小
int[][] dp= new int[w.length+1][bagV+1]; // 动态规划表
for (int i = 0; i < w.length; i++) { // 第 i 个物品
for (int j = 1; j <= bagV; j++) { // 容量
// 状态转移方程
if (j < w[i]) {
dp[i+1][j] = dp[i][j];
} else {
dp[i+1][j] = Math.max(dp[i][j], dp[i][j-w[i]] + v[i]);
}
}
}
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
// 最优解
System.out.println(dp[w.length][bagV]);
}
二、完全背包问题
题目
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
状态转移方程：
- 类似 01 背包问题，但是取策略不是取或不取，而是取 0 件、1件、2件...等
//dp[i][j] 表示前 i 件物品放入一个容量为 j 的背包可以获取的最大值
dp[i][j] = max{dp[i-1][j-k*w[i]] + k*v[i] | 0<=k*w[i]<=j}
代码：
public static void main(String[] args) {
int[] w = new int[]{2, 3, 4, 5}; // 商品的体积 2 3 4 5
int[] v = new int[]{3, 4, 5, 6}; // 商品的价值 3 4 5 6
int bagV = 8; // 背包大小
int[][] dp= new int[w.length+1][bagV+1]; // 动态规划表
for (int i = 0; i < w.length; i++) { // 第 i 个物品
for (int j = 1; j <= bagV; j++) { // 容量
// 状态转移方程
for (int k = 0; k*w[i] <= j; k++) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j-k*w[i]] + k*v[i]);
}
}
}
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
// 最优解
System.out.println(dp[w.length][bagV]);
}
三、多重背包问题
题目
有N种物品和一个容量为 V 的背包。第i种物品最多有 n[i] 件可用，每件重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法
和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第 i 种物品有 n[i]+1 种策略：取 0 件，取 1 件……取 n[i] 件。令dp[i][j] 表示前 i 种物品恰放入一个容量为 j 的背包的最大权值，则有状态转移方程：
//dp[i][j] 表示前 i 件物品放入一个容量为 j 的背包可以获取的最大值
dp[i][j] = max{dp[i-1][j-k*w[i]] + k*v[i] | 0<=k<=n[i] && 0<=k*w[i]<=j}
代码：
public static void main(String[] args) {
int[] w = new int[]{2, 3, 4, 5}; // 商品的体积 2 3 4 5
int[] v = new int[]{3, 4, 5, 6}; // 商品的价值 3 4 5 6
int[] n = new int[]{1, 3, 2, 1}; // 每件商品的数量
int bagV = 8; // 背包大小
int[][] dp= new int[w.length+1][bagV+1]; // 动态规划表
for (int i = 0; i < w.length; i++) { // 第 i 个物品
for (int j = 1; j <= bagV; j++) { // 容量
// 状态转移方程
for (int k = 0; k*w[i] <= j && k <= n[i]; k++) {
dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j-k*w[i]] + k*v[i]);
}
}
}
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
// 最优解
System.out.println(dp[w.length][bagV]);
}
四、混合三种背包问题
题目：
将前面三种背包问题混合起来，也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
01背包与完全背包的混合
一类物品只能取一次，另一类物品可以取无限次。
解决方法：判断物品种类从而进入不同的循环。
for i=1..n
if 第 i 件物品属于 01 背包
for j=1..bagV
dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]] + v[i]}
if 第 i 件物品属于 完全背包问题
for j=1..bagV
dp[i][j] = max{dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i] | 0<=k*w[i]<=j}
if 第 i 件物品属于 多重背包问题
for j=1..bagV
dp[i][j] = max{dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i] 0<=k<=n[i] && 0<=k*w[i]<=j}
五、二维费用的背包问题
题目
对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（即背包容量）。
设两种代价分别为 w1[i], w2[i], 物品的价值为 v[i]
状态转移方程
dp[i][j][k] = max{dp[i-1][j][k], dp[i-1][j-w1[i]][k-w2[i]] + v[i]}
小结
当发现熟悉的动态规划题目变形而来的题目时，在原来的状态中可以加一维度来满足新的限制是一种比较通用的方法。
