博客

public class knapsack {<br /> public static void main(String[] args){<br /> int MIN = 1;<br /> int MAX = 8;</p> <p> Fruit[] fruits={<br /> new Fruit(“李子”, 4, 4500),<br /> new Fruit(“苹果”, 5, 5700),<br /> new Fruit(“桔子”, 2, 2250),<br /> new Fruit(“草莓”, 1, 1100),<br /> new Fruit(“甜瓜”, 6, 6700)<br /> };</p> <p> int[] items = new int[MAX+1];<br /> int[] value = new int[MAX+1];</p> <p> for(int i=0;i<fruits.length;i++){<br /> for(int s = fruits[i].getSize();s<=MAX;s++){<br /> int p = s-fruits[i].getSize();<br /> int newValue = value[p] + fruits[i].getValue();<br /> if(newValue>value[s]){<br /> value[s] = newValue;<br /> items[s] = i;<br /> /* */<br /> }<br /> }</p> <p> }</p> <p> System.out.println(“物品/t价格”);<br /> for(int i = MAX;<br /> i >= MIN;<br /> i = i – fruits[items[i]].getSize()<br /> ){<br /> System.out.println(fruits[items[i]].getName()+”/t”+fruits[items[i]].getValue());<br /> /* 注意是fruits[item[i]]*/<br /> }</p> <p> System.out.println(“合计:”);<br /> System.out.println(value[MAX]);</p> <p> }