0/1背包问题(第一版)
2017-09-30 本文已影响43人
大桥酱
如果是可切分的背包问题,那没什么难度。基本上就是选择一个性价比最高的物品先放进去,放完发现没有了,然后放性价比第二高的,以此类推。

那么如果是商品无法切割。背包重量有限呢?这种情况就需要采用动态规划的思想,来完成最优的规划。
列出公式如下,如果物品质量大于袋子质量,那么就是在剩下的物品中求得最优即可。如果物品的质量小于袋子的质量,那么在两种方案中选择最优即可。

具体的代码我已经实现:
首先,我先定义了一个这样的数据结构

实际上,表示物品的价值和重量用二维数组就可以了,但Java总爱面向对象,这种自定义的数据结构会大大丰富可用性,也有较高的可移植性
每定义一个数据结构记得内部类里面写上对应的get 和 set 方法

在main函数里面获取主要的参数,并对product List进行初始化处理,为什么要进行初始化呢,因为后面要用到,背包问题的第二版我会写一个不用初始化数据的代码

这样就获得了数据
接下来最重要的一步就是对数据进行处理

其实主要是实现了上面的公式
难点在于数据的初始化,到底是从1 开始 还是 从0 开始



怎么找到具体的输出哪个选项呢
