题解报告:0-1背包问题
描述:
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0 < N,V ≤ 1000
0 < vi,wi ≤ 1000
示例:
输入:
4 5
1 2
2 4
3 4
4 5
输出:
8
代码示例:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] weight = new int[n + 1];
int[] value = new int[n + 1];
for (int i = 1; i <= n; i++) {
weight[i] = in.nextInt();
value[i] = in.nextInt();
}
int res = maxValue(value, weight, n, v);
int res2 = optimize(value, weight, n, v); // 优化后的方法
}
/**
* 动态规划:
* 定义一个二维矩阵dp[i][j]表示前i个物品,背包容量j情况下的最优解
* 在判断第i个物品时有两种情况:
* 1.第i件物品加进来比背包容量大,则不选 dp[i][j] = dp[i-1][j]
* 2.第i件物品加进来比背包容量小,则通过判断价值是否选
* 选:前i-1件物品放入容量为j-w[i]的背包中最大价值
* 不选:前i-1件物品放入容量为j的背包中最大价值
* dp[i][j] = MAX(dp[i-1][j], dp[i-][j-weight[i]]+value[i])
*/
private static int maxValue(int[] value, int[] weight, int n, int v) {
int[][] dp = new int[n+1][v+1];
for (int i = 1; i <= n; i++) { // dp[0][0-v] 都为0
for (int j = 0; j <= v; j++) { // 背包容量
if (j < weight[i]) { // 当前物品重量大于背包容量
dp[i][j] = dp[i-1][j]; // 不将物品放入背包中,所以价值还是前面的量
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
}
}
}
return dp[n][v];
}
/**
* 动态规划:一维数组
* dp[j] = Max(dp[j], dp[j-weight[i]] + value[i])
*/
private static int optimize(int[] value, int[] weight, int n, int v) {
int[] dp = new int[v + 1]; // 表示当前背包重量为j的最大价值
for (int i = 1; i <= n; i++) {
// 注意:这里是倒序进行遍历,是为了解决覆盖旧值问题,可以和完全背包问题进行比较
for (int j = v; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[j]] + value[i]);
}
}
}
}
题解报告:完全背包问题
描述:
题目如上题,只不过条件变成“每种物品都有无限件可用”。
代码示例:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] weight = new int[n + 1];
int[] value = new int[n + 1];
for (int i = 1; i <= n; i++) {
weight[i] = in.nextInt();
value[i] = in.nextInt();
}
System.out.print(optimize(value, weight, n, v));
}
/**
* 动态规划:一维数组
*/
private static int optimize(int[] value, int[] weight, int n, int v) {
int[] dp = new int[v+1];
for (int i = 1; i <= n; i++) {
// 注意:此处正序遍历,和01背包问题不同,本题物品可重复使用,因此不在乎是否使用新值
/*
首先dp数组初始化全为0:给定物品种类有4种,包最大体积为5,数据来源于题目的输入
weight value
1 2
2 4
3 4
4 5
i = 1 时: j从weight[1]到5
dp[1] = max(dp[1],dp[0]+value[1]) = value[1] = 2 (用了一件物品1)
dp[2] = max(dp[2],dp[1]+value[1]) = value[1] + value[1] = 4(用了两件物品1)
dp[3] = max(dp[3],dp[2]+value[1]) = value[1] + value[1] + value[1] = 6(用了三件物品1)
dp[4] = max(dp[4],dp[3]+value[1]) = value[1] + value[1] + value[1] + value[1] = 8(用了四件物品1)
dp[5] = max(dp[3],dp[2]+value[1]) = value[1] + value[1] + value[1] + value[1] + value[1] = 10(用了五件物品)
i = 2 时:j从weight[2]到5
dp[2] = max(dp[2],dp[0]+value[2]) = value[1] + value[1] = value[2] = 4(用了两件物品1或者一件物品2)
dp[3] = max(dp[3],dp[1]+value[2]) = 3 * value[1] = value[1] + value[2] = 6(用了三件物品1,或者一件物品1和一件物品2)
dp[4] = max(dp[4],dp[2]+value[2]) = 4 * value[1] = dp[2] + value[2] = 8(用了四件物品1或者,两件物品1和一件物品2或两件物品2)
dp[5] = max(dp[5],dp[3]+value[2]) = 5 * value[1] = dp[3] + value[2] = 10(用了五件物品1或者,三件物品1和一件物品2或一件物品1和两件物品2)
i = 3时:j从weight[3]到5
dp[3] = max(dp[3],dp[0]+value[3]) = dp[3] = 6 # 保持第二轮的状态
dp[4] = max(dp[4],dp[1]+value[3]) = dp[4] = 8 # 保持第二轮的状态
dp[5] = max(dp[5],dp[2]+value[3]) = dp[4] = 10 # 保持第二轮的状态
i = 4时:j从weight[4]到5
dp[4] = max(dp[4],dp[0]+value[4]) = dp[4] = 10 # 保持第三轮的状态
dp[5] = max(dp[5],dp[1]+value[4]) = dp[5] = 10 # 保持第三轮的状态
*/
for (int j = weight[i]; i <= v; j++) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
}
题解报告:多重背包问题
描述:
有 N 种物品和一个容量是 V 的背包,第 i 种物品最多有 si 件,每件体积 vi,价值是 wi。
求解将哪些物品装入背包,可使得物品体积总和不超过背包容量,且价值总和最大。输出最大值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包体积。
接下来有 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
思路:
可以理解为01背包问题的变种,将多个相同的物品看作个体
示例代码:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] weight = new int[n + 1];
int[] value = new int[n + 1];
int[] num = new int[n + 1];
for (int i = 1; i <= n; i++) {
weight[i] = in.nextInt();
value[i] = in.nextInt();
num[i] = in.nextInt();
}
System.out.println(maxValue(value, weight, num, n, v));
}
private static int maxValue(int[] value, int[] weight, int[] num, int n, int v) {
int[] dp = new int[v + 1];
for(int i = 1; i <= n; i++) {
for (int j = v; j >= weight[i]; j--) {
// 从一步开始,去尝试放入多个相同物品
for (int k = 1; k <= num[i]; k++) {
if (j >= k * weight[i]) {
dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
}
}
}
return dp[v];
}
}
优化:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
/* 使用二进制拆分
* 1. 普通方法是将相同的多个物品拆看成单个特例,进行逐个遍历比较,
* 但是每次都要遍历num[i]次,复杂。例如11个相同物品,需要遍历11次。
* 2.使用二进制拆分成几个数来表示1~num[i],例如1 2 4 4,可以表示1~11
* Q:那么是如何获得这几个数呢?
* 原数不断减去2的整次幂,直到最后比剩余数大,无法再减,则再加上最后一个
* 11-1=10,10-2=8,8-4=4,4>=4直接添加
*/
//构造新的value,weight
//0<V<2000,数组最大容量每个si能拆出来的个数 + 左右预留的哨兵位置 = 2000 * log2(2000) + 2 <= 22002
int maxN = 22002;
int[] weight = new int[maxN];
int[] value = new int[maxN];
int p=1;//数组索引
for (int i = 1; i <= n; i++) {
int W = in.nextInt();
int V = in.nextInt();
int S = in.nextInt();
for(int k=1;k<S;k*=2){
weight[p] = k*W;
value[p] = k*V;
S-=k;
p++;
}
if(S>0){//剩余
weight[p] = S*W;
value[p] = S*V;
p++;
}
}
System.out.println(maxValueBinary(value,weight,n,v));
}
/**
*
* @param value
* @param weight
* @param n
* @param v
* @return
*/
private static int maxValueBinary(int[] value, int[] weight, int n, int v) {
//构建好数组就变成了01背包问题
int[] dp = new int[v+1];
for(int i=1;i<=n;i++){
for(int j=v;j>=weight[i];j--){
dp[j] = Math.max( dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[v];
}
}
下面方法还没看,记得看!