如果是可切分的背包问题，那没什么难度。基本上就是选择一个性价比最高的物品先放进去，放完发现没有了，然后放性价比第二高的，以此类推。
那么如果是商品无法切割。背包重量有限呢？这种情况就需要采用动态规划的思想，来完成最优的规划。
列出公式如下，如果物品质量大于袋子质量，那么就是在剩下的物品中求得最优即可。如果物品的质量小于袋子的质量，那么在两种方案中选择最优即可。
具体的代码我已经实现：
首先，我先定义了一个这样的数据结构
实际上，表示物品的价值和重量用二维数组就可以了，但Java总爱面向对象，这种自定义的数据结构会大大丰富可用性，也有较高的可移植性
每定义一个数据结构记得内部类里面写上对应的get 和 set 方法
在main函数里面获取主要的参数，并对product List进行初始化处理，为什么要进行初始化呢，因为后面要用到，背包问题的第二版我会写一个不用初始化数据的代码
这样就获得了数据
接下来最重要的一步就是对数据进行处理
其实主要是实现了上面的公式
难点在于数据的初始化，到底是从1 开始 还是 从0 开始
怎么找到具体的输出哪个选项呢
网友评论