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.
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:
Vielleicht hat mir ja jemand einen Tipp.
mfg Kurt
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.
Java:
/**
* 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:
Java:
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
Zuletzt bearbeitet:
