01背包(dp)
【摘要】 问题描述：有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？解决这个题有两种方法，和其它的动态规划问题一样数组w[]为物品的重量，v[]为物品的价值一种是递归的思想，从后向前考虑，背包决定是否放一个物品是根据两个值的大小判断（一个值是背包没有放入这个物品的价值，另一个值是背包放入这个物品，另外背包容量减少物品重量的价值），去两个值中的最大...
问题描述：
有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
解决这个题有两种方法，和其它的动态规划问题一样
数组w[]为物品的重量，v[]为物品的价值
一种是递归的思想，从后向前考虑，背包决定是否放一个物品是根据两个值的大小判断（一个值是背包没有放入这个物品的价值，另一个值是背包放入这个物品，另外背包容量减少物品重量的价值），去两个值中的最大值，递归结束条件是物品放完或者是背包容量小于等于0。
dp
接下来就是动态规划的思想，动态规划是从前往后想
求这个背包问题首先要画一个表
横轴是容量，纵轴是物品id
求解问题的过程就是维护这个表的过程，求解的值，就是最后一个空格的值
首先对于第0号物品
容量为0时，由于自身重量为1，所以放不进去，所以空格填0，容量为1以后，该物品可以放进去了，就都为6
对于第1号物品
对于（2,1）这个位置，由于背包容量是2，所以我可以放1号物品，将0号物品拿出来，或者不放1号物品，判断两种情况下的最大值，是第一种情况。
对于（3,1）这个位置，背包容量为3，可以1,0两个物品都放，或者保持（2,1），结果两个都放是最大值。
对于第2号物品
（3,2）这个位置是（0,1）+2号物品的价值和（3,1）比大小，结果是（3,1）比较大，所以还是16
（4,2）这个位置是（1,1）+2号物品的价值和（4,1）比大小，结果是（1,1）+12大，所以为18
（5,2）这个位置是（2,1）+2号物品的价值和（5,1）比大小，结果是（2,1）+12大，所以为22
所以最后背包的最大值为22
package action;
public class demo {
public static void main(String[] args) {
int size = 5;
int[] w = { 1, 2, 3 };
int[] v = { 6, 10, 12 };
System.out.println(backpack(w, v, size));
}
public static int backpack(int[] w, int[] v, int size) {
if (w.length != v.length)
return -1;
int n = w.length;
if (n == 0)
return 0;
int[][] memo1 = new int[n][size + 1];
for (int i = 0; i <= size; i++) {
memo1[0][i] = (i >= w[0] ? v[0] : 0);
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= size; j++) {
memo1[i][j] = memo1[i - 1][j];
if (j >= w[i]) {
memo1[i][j] = Math.max(memo1[i][j], v[i] + memo1[i - 1][j - w[i]]);
}
}
}
return memo1[n - 1][size];
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）