有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。
限制条件:
1≤n≤100
1≤wi,vi≤100
1≤W≤10000
例如输入:
n = 4
W=5
2 3 (分别为w,v)
1 2
3 4
2 2
输出
7
如果是普通的递归,搜索的深度就是n,并且每一层的搜索都需要2次分支,n比较大的时候就没办法解
第二种就是动态规划表(也可以用递归版的动态规划),这里
weight[4]={2,1,3,2}
value[4] = {3,2,4,2}
dp[i][j]表(最大价值表),代表获得最大价值的递推关系表
i \ j | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 7 | 6 | 5 | 3 | 2 | 0 |
1 | 6 | 6 | 4 | 2 | 2 | 0 |
2 | 6 | 4 | 4 | 2 | 0 | 0 |
3 | 2 | 2 | 2 | 2 | 0 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 |
从右下往左上,j是背包已经装的重量,加上weight[i]重量的物品能够获得的最大价值,最底下一行作为辅助空间。
思路是:已经装了重量j时,是否还可以装入第i件物品weight[i]的重量。
dp[i][j]意思是从后往前在计算第i件物品时能装入的最大价值,dp[0][0]就是从后往前遍历完之后到第0件物品能装入的最大价值。也就是我们需要求的最大价值。
weight[0]表示第零件物品的重量。
从i=3开始,如果已经装的重量为5,什么都装不了,价值为0。
i=3时:
若j=4,背包已经装了4重量时,是否可以装下第三件物品重量weight[3]=2呢?j+weight[3]=4+2=6>5,所以不可以。这里最大价值dp[3][4]=0。
若j=3,背包已经装了3重量时,是否可以装下第三件物品重量weight[3]=2呢?j+weight[3]=3+2=5可以!获得了价值value[3]=2。所以最大价值dp[3][3]=2。
若j=2..j=1...j=0也是一样,第三件物品的重量weight[3]=2都可以放下,也就是背包已经装了3重量,2重量,1重量,0重量时,在这个步骤再装还能获得的最大价值为2。所以同样的最大价值dp[3][2]=dp[3][1]=dp[3][0]=2。
i=2时:
若j=5,背包已达最大重量,什么都装不了,最大价值为0!
若j=4,背包已经装了4重量时,是否可以装下第2件物品重量weight[2]=3?j+weight[2]=4+3=7 > W=5,装不了第2件物品,那么只好听从上一步结果,最大价值为dp[2][4]=dp[3][4]=0。
若j=3,背包已经装了3重量时,是否可以装下第2件物品重量weight[2]=3?j+weight[2]=3+3=6 > W=5,装不了第2件物品,那么只好听从上一步结果,最大价值为dp[2][3]=dp[3][3]=2。
若j=2,背包已经装了2重量时,是否可以装下第2件物品重量weight[2]=3?j+weight[2]=2+3<=5成立,能装第2件物品!那么在上一步装的基础上再装weight[2],重量就是2+weight[2]。最大价值为dp[2][2]=value[2]+dp[3][2+weight[2]=5]=4+0=4;即最大价值dp[2][2]=max(dp[2][2], 4+dp[3][5])=4。而dp[2][2]我们可以先将dp[3][2]的值赋给它,这样就是可以比较装weight[2]时(此时价值value[2]+dp[3][2+weight[2]])和不装weight[2]时(此时价值dp[3][2])最大价值的区别。那dp[3][2+weight[2]]又是什么意思?刚刚我们从表的底部往上的时候计算了第3行的呀,就是在上一步计算出的在对应位置能获得的最大价值,既然上一步算过了,这一步还操什么心?现在就只看i=2时的第二行!!!
若j=1,背包已经装了1重量时,是否可以装下第2件物品重量weight[2]=3?或者第三件物品重量weight[3]=2?但是无法同时装下2样。
如果装weight[3]=2,那么价值value[3]为2,dp[2][1]=max(dp[2][1], value[3]+dp[3][1+weight[3]=3])。即dp[2][1]=max(dp[2][1],
2+dp[3][3])=4。
如果装备weight[2]=3,value[2]=4,那么价值为dp[2][1]=max(dp[2][1], value[2]+dp[3][1+weight[2]=4])。即dp[2][1]=max(dp[2][1], 4+dp[3][4])=4。两种情况的最大价值均为4,其实不同只有剩余背包的可装重量不同,前者还剩2,后者还剩1。
若j=0,背包已经装了0重量时,是否可以装下第2件物品重量weight[2]=3?可以装上第二件weight[2]=3和第三件weight[3]=2,装上之后总重量正好为5,所以此时的总价值是value[2]+value[3]=4+2=6,那么价值dp[2][0]=max(dp[2][0],
value[2]+dp[3][0+weight[2]=3])=max(dp[2][0], 4+dp[3][3])=6。
而dp[3][3]在我们从下往上计算的时候已经算过了,不管是什么意思,反正刚刚一定正确计算了(因为上一步单独算过只装第三件weight[3]了,此时只算装上第二件weight[2]就行了),直接用。
dp[2][0]=max(dp[2][0], 4+2)=6。
显然两件同时装比只装其中一件获得的总价值更高。
......同理推到左上,动笔记录打草稿,这样才看的懂意思,这个确实很难理解
最后dp[0][0]=max(dp[0][0], value[0]+dp[1][0+weight[0]=2]),即dp[0][0]=max(dp[0][0], 3+4)=7。
import java.io.BufferedInputStream;
import java.util.Scanner;
public class test {
public static int[] weight = new int[101];
public static int[] value = new int[101];
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int n = cin.nextInt();
int W = cin.nextInt();
for (int i = 0; i < n; ++i) {
weight[i] = cin.nextInt();
value[i] = cin.nextInt();
}
cin.close();
System.out.println(solve(0, W, n)); // 普通递归
System.out.println("=========");
System.out.println(solve2(weight, value, W)); // 动态规划表
}
public static int solve(int i, int W, int n) {
int res;
if (i == n) {
res = 0;
} else if (W < weight[i]) {
res = solve(i + 1, W, n);
} else {
res = Math.max(solve(i + 1, W, n), solve(i + 1, W - weight[i], n) + value[i]);
}
return res;
}
public static int solve2(int[] weight, int[] value, int W) {
int[][] dp = new int[weight.length + 1][W + 1];
for (int i = weight.length - 1; i >= 0; --i) {
for (int j = W; j >= 0; --j) {
dp[i][j] = dp[i + 1][j]; // 从右下往左上,i+1就是刚刚记忆过的背包装到i+1重量时的最大价值
if (j + weight[i] <= W) { // dp[i][j]就是背包已经装了j的重量时,能够获得的最大价值
dp[i][j] = Math.max(dp[i][j], value[i] + dp[i + 1][j + weight[i]]);
// 当背包重量为j时,要么沿用刚刚装的,本次不装,最大价值dp[i][j],要么就把这个重物装了,那么此时背包装的重量为j+weight[i],
// 用本次的价值value[i]加上背包已经装了j+weight[i]时还能获得的最大价值,因为是从底下往上,刚刚上一步算过,可以直接用dp[i+1][j+weight[i]]。
// 然后选取本次不装weight[i]重物时获得的最大价值以及本次装weight[i]重物获得的最大价值两者之间的最大值
}
}
}
return dp[0][0];
}
}