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.
1
/**
2
* Efficient array of booleans.
3
*
4
* The booleans are stored in an integer. Starting from the less significant bit up to
5
* the index {@link Selection#size()} the respective boolean is true iff the bit is 1.
6
*
7
* The values of all other bits are undefined.
8
*/
9
public class Selection {
10
private int bits;
11
private int size;
12
13
/**
14
* Create a selection
15
* @param size the size of the selection
16
* @param bits the values of the booleans encoded as integer
17
*/
18
public Selection(int size, int bits)
19
{
20
setSize(size);
21
setBits(bits);
22
}
23
24
/**
25
* Create a selection with all booleans set to false
26
*
27
* @param size the size of the selection. 0 <= size <= 32.
28
*/
29
public Selection(int size)
30
{
31
setSize(size);
32
setBits(0);
33
}
34
35
/**
36
* Set the boolean values
37
*
38
* @param bits the boolean values encoded as integer.
39
*/
40
public void setBits(int bits)
41
{
42
this.bits = bits;
43
}
44
45
/**
46
* Get the boolean values
47
*
48
* @return the boolean values encoded as integer.
49
*/
50
public int bits()
51
{
52
return bits;
53
}
54
55
/**
56
* Set the size of the selection.
57
*
58
* If the size is increased the values of the new booleans are undefined.
59
*
60
* @param size the new size of the selection. 0 <= size <= 32
61
*/
62
public void setSize(int size)
63
{
64
if (size > 32) throw new IllegalArgumentException("a maximum of 32 bits is supported only");
65
if (size < 0) throw new IllegalArgumentException("the size must be greater or equal to zero");
66
this.size = size;
67
}
68
69
/**
70
* Get the size of the selection
71
* @return the size of the selection
72
*/
73
public int size()
74
{
75
return size;
76
}
77
78
/**
79
* Set a boolean value
80
*
81
* @param index the index of the boolean
82
* @param value the value of the boolean
83
*/
84
public void set(int index, boolean value)
85
{
86
if (index < 0 || index >= size) {
87
throw new IndexOutOfBoundsException();
88
}
89
if (value) {
90
int mask = 1 << index;
91
bits = bits | mask;
92
} else {
93
int mask = ~(1 << index);
94
bits = bits & mask;
95
}
96
}
97
98
/**
99
* Get a boolean values
100
*
101
* @param index the index of the boolean
102
* @return the value of the selected boolean
103
*/
104
public boolean get(int index)
105
{
106
if (index < 0 || index >= size) {
107
throw new IndexOutOfBoundsException();
108
}
109
int mask = 1 << index;
110
return (bits & mask) != 0;
111
}
112
113
public String toString()
114
{
115
StringBuffer buf = new StringBuffer();
116
buf.append("[");
117
for (int i=0; i<size; i++) {
118
if (i != 0) buf.append(", ");
119
if (get(i)) {
120
buf.append("true");
121
} else {
122
buf.append("false");
123
}
124
}
125
buf.append("]");
126
return buf.toString();
127
}
128
129
/**
130
* Calculates a selected sum
131
* @param addends a vector of integers. The vector must be as large as the selection.
132
* @return the sum of all addends for which the corresponding booleans are true.
133
*/
134
public int sum(ArrayList<Integer> addends)
135
{
136
if (addends.size() != size()) throw new IllegalArgumentException("Not enough or too many addends");
137
int sum = 0;
138
for (int i=0; i<addends.size(); i++) {
139
if (get(i)) {
140
sum += addends.get(i);
141
}
142
}
143
return sum;
144
}
145
}
Was ich bisher habe:
1
public class RucksackBacktracking implements IRucksack {
2
3
//Find an optimal solution for the Rucksack problem with "Backtracking"!
4
5
public Selection findBest(ArrayList<Integer> values,
Ja, die Grösse ist konstant, aber der Konstruktor initialisiert dir
deine ganze Selection, welche ja als Int repräsentiert wird.
Du musst also dass, was du schon in früheren "Rekursionen" gemacht hast
benutzen. So in etwa without = new Selection(values.size(), sel.bits())
damit du die ersten n-Elemente berücksichtigst.
Das "jeweilige" Bit setzt du dann ja mit dem: with.set(i, true);
lg
Und damit das Programm auch schnell läuft für größere Eingaben, sollte
man mal über dynamische Programmierung nachdenken ;) sonst läuft das
Teil in exponentieller Laufzeit
Eine eigene Frage?
Dieser Thread ist über 14 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
