Rucksack Problem

gistfile1.java

import java.util.ArrayList;



public class Rucksack {
	private ArrayList<Item> items=new ArrayList<Item>();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Rucksack rs=new Rucksack();
		rs.add("Wood",100,1000);
		rs.add("Gold",50,1000);
		rs.add("Diamond",50,10000);
		
		for (int i = 0; i <12; i++) {
			rs.add("Random Item "+i,(int)( Math.random()*400d+50),(int)( Math.random()*4000d+50));
		}
		rs.solve(500);
		rs.quicksolve(500);
	}

	private void quicksolve(int max_weight) {
		int max_value=0;
		for(Item i:items){
			max_value+=i.approximate_value;
		}
		System.out.println();System.out.println();
		System.out.println("Problem Size "+(max_value*items.size()));
		int[][] mingewicht=new int[items.size()+1][max_value+1];
		for (int i = 0; i < mingewicht.length; i++) {
			 
			for (int j = 0; j < mingewicht[i].length; j++) {
			 
				mingewicht[i][j]=(j==0?0:100000);
				 
			}
		}
		int citem=0;
		int cvalue=0;
		for (int i = 1; i < mingewicht.length; i++) {
			for (int w = 1; w < mingewicht[i].length; w++) {
				mingewicht[i][w]=mingewicht[i-1][w];
				Item current_item=items.get(i-1);
				if(current_item.approximate_value<=w&&mingewicht[i-1][w-current_item.approximate_value]+current_item.weight<=mingewicht[i][w]){
					mingewicht[i][w]=mingewicht[i-1][w-current_item.approximate_value]+current_item.weight;
					if(mingewicht[i][w]<=max_weight&& w>cvalue){
						citem=i;
						cvalue=w;
					}
				}
			}
		}
		System.out.println("Quick Result: "+mingewicht[citem][cvalue]);
		//Walkback
		
		while(citem>0){
			Item current_item=items.get(citem-1);
			if(current_item.approximate_value<=cvalue&&mingewicht[citem][cvalue]==mingewicht[citem-1][cvalue-current_item.approximate_value]+current_item.weight){
				System.out.println("Take:"+current_item.name);
				citem--;
				cvalue-=current_item.approximate_value;
				
			}else{
				//System.out.println("Do not take:"+current_item.name);
				citem--;
				
			}
		}
	}

	private void solve(int max_weight) {
		int[][] maxwert=new int[items.size()+1][max_weight+1];System.out.println();System.out.println();
		System.out.println("Problem Size "+(max_weight*items.size()));
		for (int i = 1; i < maxwert.length; i++) {
			for (int g = 1; g < maxwert[i].length; g++) {
				maxwert[i][g]=maxwert[i-1][g];
				Item current_item=items.get(i-1);
				if(current_item.weight<=g&&maxwert[i-1][g-current_item.weight]+current_item.value>=maxwert[i][g]){
					maxwert[i][g]=maxwert[i-1][g-current_item.weight]+current_item.value;
				}
			}
		}
		System.out.println("Result:"+maxwert[items.size()][max_weight]);
		//Walkback
		int citem=items.size();
		int cweight=max_weight;
		while(citem>0){
			Item current_item=items.get(citem-1);
			if(maxwert[citem][cweight]==maxwert[citem-1][cweight]){
				
				//System.out.println("Do not take:"+current_item.name);
				citem--;
			}else{
				System.out.println("Take:"+current_item.name);
				citem--;
				cweight-=current_item.weight;
			}
		}
	}

	private void add(String name, int weight, int value) {
		// TODO Auto-generated method stub
		System.out.println("Item: "+name+" Weight:"+weight+" Value:"+value);
		items.add(new Item(name,weight,value));
	}

	class Item{

		private String name;
		private int weight;
		private int value;
		private int approximate_value;

		public Item(String name, int weight, int value) {
			this.setName(name);
			this.setWeight(weight);
			this.setValue(value);
		}

		public String getName() {
			return name;
		}

		public void setName(String name) {
			this.name = name;
		}

		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;
			this.approximate_value=(int)Math.round(value/250d);
		}
		
		
	}
}