# Backtracking Rucksackproblem



## kurtisblow (8. Mai 2012)

Hallo,
ich komme bei folgender Aufgabe nicht klar:
Wir sollen einen "Rucksack" durch das Backtrackingverfahren packen, sprich
man soll die Gegenstände mit den höchsten Wert finden, die aber eine gewisse
Gewichtsschranke nicht überschreiten dürfen.

Nun haben wir folgende Selection Klasse, wo wir die einzelnen
methoden, z.B sum(weights) für das aktuell Gewicht im Rucksack aufrufen können.


```
/**
 * Efficient array of booleans.
 * 
 * The booleans are stored in an integer.  Starting from the less significant bit up to 
 * the index {@link Selection#size()}  the respective boolean is true iff the bit is 1.
 * 
 * The values of all other bits are undefined.
 */
public class Selection {
	private int bits;
	private int size;

	/**
	 * Create a selection
	 * @param size the size of the selection
	 * @param bits the values of the booleans encoded as integer
	 */
	public Selection(int size, int bits)
	{
		setSize(size);
		setBits(bits);
	}
	
	/**
	 * Create a selection with all booleans set to false
	 * 
	 * @param size the size of the selection. 0 <= size <= 32.
	 */
	public Selection(int size) 
	{
		setSize(size);
		setBits(0);
	}

	/**
	 * Set the boolean values
	 * 
	 * @param bits the boolean values encoded as integer.
	 */
	public void setBits(int bits)
	{
		this.bits = bits;
	}
	
	/**
	 * Get the boolean values
	 * 
	 * @return the boolean values encoded as integer.
	 */
	public int bits()
	{
		return bits;
	}
	
	/**
	 * Set the size of the selection.
	 * 
	 * If the size is increased the values of the new booleans are undefined.
	 * 
	 * @param size the new size of the selection. 0 <= size <= 32
	 */
	public void setSize(int size)
	{
		if (size > 32) throw new IllegalArgumentException("a maximum of 32 bits is supported only");
		if (size < 0) throw new IllegalArgumentException("the size must be greater or equal to zero");
		this.size = size;
	}

	/**
	 * Get the size of the selection
	 * @return the size of the selection
	 */
	public int size()
	{
		return size;
	}
	
	/**
	 * Set a boolean value
	 * 
	 * @param index the index of the boolean
	 * @param value the value of the boolean
	 */
	public void set(int index, boolean value)
	{
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		if (value) {
			int mask = 1 << index;
			bits = bits | mask;
		} else {
			int mask = ~(1 << index);
			bits = bits & mask;
		}
	}
	
	/**
	 * Get a boolean values
	 * 
	 * @param index the index of the boolean
	 * @return the value of the selected boolean
	 */
	public boolean get(int index)
	{
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}
		int mask = 1 << index;
		return (bits & mask) != 0;
	}
	
	public String toString()
	{
		StringBuffer buf = new StringBuffer();
		buf.append("[");
		for (int i=0; i<size; i++) {
			if (i != 0) buf.append(", ");
			if (get(i)) {
				buf.append("true");
			} else {
				buf.append("false");
			}
		}
		buf.append("]");
		return buf.toString();
	}
	
	/**
	 * Calculates a selected sum
	 * @param addends a vector of integers. The vector must be as large as the selection.
	 * @return the sum of all addends for which the corresponding booleans are true.
	 */
	public int sum(ArrayList<Integer> addends)
	{
		if (addends.size() != size()) throw new IllegalArgumentException("Not enough or too many addends");
		int sum = 0;
		for (int i=0; i<addends.size(); i++) {
			if (get(i)) {
				sum += addends.get(i);
			}
		}
		return sum;
	}
}
```

Nach Brute Force habe ich es bereits implementiert, nur weiss ich einfach nicht wie ich es mit Backtracking machen sollen.

Mein bisheriger Ansatz sieht so aus:


```
public class RucksackBacktracking implements IRucksack {

	//Find an optimal solution for the Rucksack problem with "Backtracking"!
	private Selection sel = new Selection(0);
	private int n = 0;
	
	public Selection findBest(ArrayList<Integer> values,
			ArrayList<Integer> weights, int maxWeight) 
	{ 
		sel = find(null,0,values,weights,maxWeight);
		return sel;
	}
	
		public Selection find(Selection currentSel,int currentWeight,ArrayList<Integer> values,
			ArrayList<Integer> weights, int maxWeight)
	{
		if(currentSel.size() == values.size())
		{
			return currentSel;
		}
		
		else if() // Sich für den Teilbaum ohne diesen Gegestand entscheiden.
		{
			n = n+1;
			Selection without = new Selection(values.size(),n);
			without.set(n-1, false);
			return find(without,currentSel.sum(weights),values,weights,maxWeight);
		}

		else () // Sich für den Teilbaum mit diesem Gegestand entscheiden.
		{
			n = n+1;
			Selection with = new Selection(values.size(),n);
			with.set(n-1,true);
			return find(with,currentSel.sum(weights),values,weights,maxWeight);
		}
	}

}
```

Vielleicht hat mir ja jemand einen Tipp.

mfg Kurt


----------



## Firephoenix (8. Mai 2012)

Hi,
versuch erstmal das vorgehen so zu verstehen, dass du es auf dem Papier per Backtracking lösen kannst, dabei dürfte das hier helfen:
Rucksackproblem ? Wikipedia

Eine andere gute Quelle die ich gefunden habe:
http://wwwiti.cs.uni-magdeburg.de/iti_db/lehre/algds0506/handout13.pdf

Gruß


----------



## kurtisblow (8. Mai 2012)

Ok, danke,
jetzt funktioniert es schon einmal teilweise für leere Rucksäcke und Rucksäcke die keine Gewicht haben dürfen.


```
public Selection findBest(ArrayList<Integer> values,
			ArrayList<Integer> weights, int maxWeight) 
	{ 
		return find(new Selection(values.size(),0),0,values,weights,maxWeight);
	}
	
	public Selection find(Selection s,int i,ArrayList<Integer> values,
			ArrayList<Integer> weights, int maxWeight)
	{
		if(i == values.size()) return s;
		Selection without = new Selection(values.size(), 0);
		without = find(without,i + 1,values,weights,maxWeight);
		
		if((s.sum(weights) + weights.get(i)) <= maxWeight) 
		{
			Selection with = new Selection(values.size(), 0);
			with.set(i, true);
			with = find(without,i + 1,values,weights,maxWeight);
			if (with.sum(values) >= without.sum(values)) return with;
		}
		return without;
	}
```

Ich such nun noch nach Fehlern, vielleicht sieht ja gerade jemand von euch einen 
Gruss Kurt


----------



## kamuikoba (8. Mai 2012)

```
public Selection findBest(ArrayList<Integer> values,
			ArrayList<Integer> weights, int maxWeight) {

		return find(new Selection(values.size(), 0), 0, values, weights,
				maxWeight);
	}

	public Selection find(Selection selection, int weight,
			ArrayList<Integer> values, ArrayList<Integer> weights, int maxWeight) {

		int i = selection.size();
		if (selection.size() == values.size()) {
			return new Selection(selection.sum(values), selection.bits());
		} else {
			Selection without = new Selection(i + 1, selection.bits());
			without = find(without, weight, values, weights, maxWeight);

			if ((weight + weights.get(i)) <= maxWeight) {
				Selection with = new Selection(i + 1, selection.bits());
				with.set(i, true);
				with = find(with, weight, values, weights, maxWeight);
				if (with.sum(values) > without.sum(values)) {
					return with;
				}
			}
			return without;
		}

	}
}
```

Hab die gleiche Aufgabe, aber kriege den Fehler: result vector ist too small or too large: expectet <3> but was <0>
Kann mir da vielleicht jemand helfen? ich komm nit auf den Fehler :/


----------

