————— 第二天—————
————————————
. . . . . . . .
让我们回到刚才的主题，假设背包的容量为10，并且有五个项目可供选择，每个项目的价值和重量如图所示：
我们来计算每件商品的性价比，结果如下：
毫无疑问，此时性价比最高的是项目4，我们把项目4放进背包里，背包剩余容量是8：
我们选择项目1放在背包里，背包的剩余容量是4：
所以我们选择了0.8件5件放在背包里，背包的剩余容量是0：
public static void main（String[] args） {
int 容量 = 10;
int[] 权重 = {4，6，3，2，4};
int[] 值 = {9，3，1，6，4};
System.out.println （"Backpack Max Value： "getHighestValue （capacity， weights， values））;
}
公共静态双精度 getHighestValue（int capacity， int[] weights，int[] values）{
创建项目列表，并按相反顺序
List<Item> itemList = new ArrayList<>（）;
for（int i=0; i<weights.length; i++）{
itemList.add（new Item（weights[i]， values[i]））;
itemList = itemList.stream（）.sorted（Comparator.comparing（Item：：getRatio）.reversed（））.collect（Collectors.toList（））;
背包剩余容量
int restCapacity = capacity;
当前背包物品的最大价值
双精度最高值 = 0;
从高到低性价比中选择项目
for（项目项目 ： 项目列表）{
if（item.weight <= restCapacity）{
最高值 += 项值;
restCapacity -= item.weight;
}else{
在背面包装未完成时选择项目的一部分
最高值 += （双倍）restCapacity / （double）item.weight * item.value;
休息;
返回最高值;
静态类项 {
私人整数重量;
私有整数值;
商品的性价比
私人双倍比率;
公共项目（整数权重，整数值）{
这个重量= 重量;
this.value = value;
这个比率 = （双倍）值 / （双倍）重量;
public double getRatio（） {
回报率;
在此代码中，我们使用静态内部类 Item 来更轻松地记录性价比、获取权重和价值信息以及对性价比进行排序。
仍然有一个可容纳10人的背包，有三个项目可供选择：
这次我们有一个条件限制：只允许选择整个项目，而不是项目的一部分。
如果按照贪婪的思维算法，第一选择是性价比最高的物品1，那么背包的剩余容量是4，没有其他物品可以装载，此时的总价值是6：
但这样的选择真的能最大化总价值吗？如果我们不选择项目 1、项目 2 和项目 3，则剩余容量为 0，总值为 7：
显然，7>6，依赖于贪婪的算法结果，不一定是全局最优解。
对于01背包问题，我们可以用动态规划算法来解决，有兴趣的小伙伴可以微信搜索"程序员小灰"，有一个动态规划算法的解释。