贪心算法求背包问题
1.定义数组 int[] packMoneyArr 用于存储行遍历的不同背包容量下的价值最大值
2.定义物品数组 Thing thing = new Thing(curVo, curMoney); 用于计算在每一个最大值对应的固定容量的包的情况下,其容量还能否支撑其添加新的物品,若能添加,则将添加后的值和原值比较,更新最大值;
package 背包问题之贪心算法; import java.util.Scanner; public class Package { /* * 背包总容量6 * * 三组数据 * 容量3 价值5 * 容量2 价值4 * 容量4 价值2 * * */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); /* * 背包容量 * * */ System.out.print("请输入背包最大重量:"); int packMax = scanner.nextInt(); System.out.print("请输入背包容纳物品数:"); int n = scanner.nextInt(); Thing[] things = new Thing[n]; for (int i = 0; i < n; i++) { System.out.print("请输入第"+(i+1)+"个商品的重量"); int curVo = scanner.nextInt(); System.out.print("请输入第"+(i+1)+"个商品的价值"); int curMoney = scanner.nextInt(); Thing thing = new Thing(curVo, curMoney); things[i] = thing; } /*定义数组,保存背包每一个体积对应的价值*/ int[] packMoneyArr = new int[packMax + 1]; //存储每个背包容量的最大值数组 for (int j = 0; j < n; j++) { //按行遍历,得到不同容量背包对于第I个物品的存储情况 for (int k = packMax; k > 0; k--) { int max = packMoneyArr[k]; // 当前容量k的最大价值初始化为之前记录的最大价值 int packLeft = k - things[j].vo;//剩余容量 if (packLeft >= 0 && max < things[j].money + packMoneyArr[packLeft]) { //剩余容量大于0 且 最大值小于当前物品的价值加上之前背包内物品的价值 max = things[j].money + packMoneyArr[packLeft]; //将最大值替换为原本物品价值+可放入物品价值的总和 } if (max > packMoneyArr[k]) { // 如果更新后的最大价值大于当前容量k之前的最大价值,则更新 packMoneyArr[k] = max; } } } System.out.println(packMoneyArr[packMax]); } } class Thing { int vo;// 容量 int money;// 价值 public Thing(int vo, int money) { this.vo = vo; this.money = money; } }标签:...,背包,容量,int,Thing,packMoneyArr,8.14,价值 From: https://blog.csdn.net/weixin_51721783/article/details/141174199