大家好，小信来为大家解答以上问题。背包问题解法，背包问题很多人还不知道，现在让我们一起来看看吧！
1、 假设背包的最大容量是W，N件物品，每件物品都有自己的价值和重量，把物品放在背包里会使背包里物品的总价值最大化。
2、 背包问题维基
3、 想象这样一个场景：3354。一个小偷在房子里偷东西。他背着一个背包。房间里的物品数量是有限的。——每件物品都有一定的重量和价值。——珠宝重量轻但价值高。桌子
4、 重但价值低。最重要的是小偷的背包容量有限。很明显，他不能把桌子一分为二或者拿走3/4的珠宝。对于一件物品，他只能选择拿还是不拿。
5、 示例：
6、 背包最大重量：W=10(单位)
7、 项目总数：N=4
8、 项目的值：v[]={10，40，30，50}
9、 物品重量：w[]={5，4，6，3}
10、 从实例数据粗略估算，最大重量为10时，背包能装的物品最大值为50 40=90，重量为7。
11、 最好的解决方法是用动态规划——得到问题的局部解，然后扩展到全局解。
12、 以不同的权重构造项目X的值数组V(值数组):
13、 V[N][W]=4行* 10列
14、 这个矩阵中每个值的解代表一个更小的背包问题。
15、 初始情况1:对于0列，表示背包的容量为0。此时该物品的价值是多少？没有。因此，第一列用零填充。
16、 初始情况2:对于0线，表示家里没有物品。那么一个没有任何物品的背包有什么价值呢？还是不行！都是零。
17、 1.现在，开始填充数组中每行的值。第一行第一列是什么意思？第一件物品，可以把重量为1的物品放进背包吗？不会吧。第一件物品的重量是5。因此，填写0。其实0要一直填到第五列(权重5)。2.对于第1行第5列(重量5)，表示将物品1放入背包。填入10(注意这是一个值数组):
18、 3.继续。对于第6列，我们是否可以放入另一个权重为1的项目(权重值-项目的权重)？现在我们只考虑第一项。由于我们在添加第1项后不能添加额外的权重，因此可以直观地看到，其余的列应该仍然具有相同的值。
19、 4.然后，有趣的事情就会发生。在第3行第4列，权重是4。
20、 做出如下判断：
21、 1.你能加入第二项吗？——是的。2的重量是4。
22、 2.如果不添加项目2，当前已有项目的权重值是否更大？——找到相同重量时，检查前一行的值。不可以，上一行的值是0，权重为4时不能放置物品1。
23、 3.能不能在这个重量里放两个物品，让价值最大化？3354不行。此时重量减去物品2的重量为0。
24、 简单来说，前面那条本身重量为4的线的值更小背包问题解，表示背包中物品最多到这个重量的最大值(通过遍历物品得到)。
25、 例如：
26、 当前项目值=40
27、 当前项目权重=4
28、 剩余重量=4-4=0
29、 查看顶行(项目1或其余行的值)。剩余容量为0时，是否可以再次持有项目1？对于给定的重量值，上述行中有值吗？
30、 计算过程如下：
31、 1)计算物品未放入时的最大重量值：
32、 前一行，相同权重=0
33、 =V[项目-1][重量]
34、 2)计算当前项目的值可以容纳的剩余重量的值
35、 当前项目的值
36、 前一行中权重为4的值(到目前为止的总权重(4) -当前项目的权重(4))
37、 =val[项目-1]V[项目-1][weight-wt[项目-1]]
38、 求其中最大值40(0和40)。
39、 3)下次最重要的位置是第2行第9列。这意味着权重是9。放入两件物品。根据示例数据，现在可以放入两个项目。我们做出如下判断：
40、 1.当前项目的值=40
41、 2.当前项目的权重=4
42、 3.剩下的重量=9 - 4=5
43、 4.检查上面一行。在剩余重量为5的情况下，我们能够
44、 未添加物品时，该重量的最大值：
45、 前一行，相同重量=10
46、 计算当前项目的值和可容纳的剩余重量的值。
47、 当前项目的值(40)
48、 前一行中权重为5的值（到目前为止的总权重(9) -当前项目的权重(4))
49、 =10
50、 10vs50=50。
51、 解决了所有的子问题之后，返回V[N][W]的值——4件物品重量为10时：
52、 解法的复杂度非常直观。在普通次循环中有W次循环=O(西北)
53、 背包类{
54、 公共静态void main(String[] args)引发异常{
55、 int val[]={10，40，30，50 }；
56、 int wt[]={5，4，6，3 }；
57、 int W=10
58、 系统。出去。println(backpackage(val，wt，W))；
59、 }
60、 public static int backpack(int val[]，int wt[]，int W) {
61、 //获取项目总数。
62、 //可能是重量长度或阀门长度.这无关紧要
63、 int N=重量长度；
64、 //创建一个矩阵。
65、 //项目按行排列，每侧第一列的权重为
66、 int[][]V=new int[N 1][W 1]；
67、 //如果背包的容量是0集呢
68、 //第0行的所有列都为0
69、 for(int col=0；col=W；col ) {
70、 v[0]div class=' column col-1-2 ' p/p/div=0；
71、 }
72、 //家里没有物品怎么办。
73、 //用0填充第一行
74、 for(int row=0；row=N；row ) {
75、 v[row][0]=0；
76、 }
77、 for(int item=1；item=N；项目){
78、 //让我们逐行填充这些值
79、 for(int weight=1；重量=W；重量){
80、 //当前项目的重量减少了吗
81、 //大于或等于运行重量
82、 if(wt[item-1]=重量){
83、 //给定一个权重，检查当前
84、 //我们能负担得起的项目的项目值
85、 //剩余重量大于该值
86、 //没有当前项本身
87、 v[项目][重量]=数学。max(val[item-1]V[item-1][weight-wt[item-1]]，V[item-1][weight])；
88、 }
89、 否则{
90、 //如果当前项的权重大于
91、 //运行重量，只是结转数值
92、 //没有当前项目
93、 五[项目][重量]=V[项目-1][重量];
94、 }
95、 }
96、 }
97、 //打印矩阵
98、 for (int[] rows : V) {
99、 for (int col : rows) {
100、 System.out.format(']'，col)；
101、 }
102、 系统。出去。println()；
103、 }
104、 return V[N][W]；
105、 }
106、 }
本文到此结束，希望对大家有所帮助。
标签：
免责声明：本文由用户上传，如有侵权请联系删除！