展示型建站模板平台,wordpress小工具,成都网站建设与维护,怎么样让百度收录网站介绍
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
分析 优化后的代码
public class demo {static class Item{int index;String na…介绍
有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
分析 优化后的代码
public class demo {static class Item{int index;String name;int weight;int value;Item(int index,String name,int weight,int value){this.indexindex;this.namename;this.weightweight;this.valuevalue;}}public static void main(String[] args) {//对象数组Item[] items new Item[]{new Item(1,黄金,4,1600),new Item(2,宝石,8,2400),new Item(3,白银,5,30),new Item(4,钻石,1,10_000),};System.out.println(select(items,10));}public static int select(Item[] items,int total){//dp数组临时存储int[] dp new int[total1];//拿到第一行item对象黄金处理Item item0 items[0];for (int i 0; i total1 ; i) {if (i item0.weight) {dp[i] item0.value;}else {dp[i]0;}}System.out.println(Arrays.toString(dp));//其余item处理for (int i 1; i items.length ; i) {Item item items[i];//内部必须从右往左计算 使用一维数组时for (int j total; j 0 ; j--) {if (j item.weight) { //装得下比较当前价值剩余容量能装下价值 VS 上一行对应列的价值dp[j] Math.max(item.valuedp[j-item.weight],dp[j]);}}System.out.println(Arrays.toString(dp));}return dp[total];}
}
运行结果
