背包问题

背包问题有很多种，简单背包，物品有价值的背包。下面是个有价值背包的代码。很久以前写的。

import java.util.LinkedList;import java.util.List;public class ItemWithWeight {/** * @param args */private static Item[] items;private static int m = 10;public static void main(String[] args) {init();Result currentValue = knap(m,items.length-1);System.out.println(currentValue.getCount());System.out.println(currentValue.getResult());}private static Result knap(int m,int position) {if (position<0) {// the list contains nothingreturn new Result();}int surplus = m - items[position].getWeight();if (surplus >=0){//if we choose this oneResult choose = knap(surplus, position-1);//put current one in the listchoose.addResult(position);choose.addCount(items[position].getValue());//if we did not choose oneResult notChoose = knap(m, position-1);if (choose.getCount() - notChoose.getCount() >= 0) {return choose;} else {return notChoose;}} else {//if the surplus is smaller than 0//we can not choose this onereturn knap(m, position-1);}}private static void init() {items = new Item[11];items[0] = new Item(1,4);items[1] = new Item(2,5);items[2] = new Item(3,12);items[3] = new Item(24,354);items[4] = new Item(5,6);items[5] = new Item(6,22);items[6] = new Item(7,8);items[7] = new Item(8,1);items[8] = new Item(15,200);items[9] = new Item(15,87);items[10] = new Item(30,245);}private static class Item{public Item(int weight,int value) {this.weight = weight;this.value = value;}int weight;int value;public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}@Overridepublic String toString() {return weight+","+value;}}private static class Result{private List<Integer> result = new LinkedList<Integer>();private int count = 0;public List<Integer> getResult() {return result;}public void setResult(List<Integer> result) {this.result = result;}public int getCount() {return count;}public void setCount(int count) {this.count = count;}public void addCount(int value) {this.count+=value;}public void addResult(int itemNo) {this.result.add(itemNo);}}}