0/1 Knapsack Problem Dynamic Programming
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Drawing graph
int[] plot(int[] values, int[] weights, int numberOfItems, int capacity) {
int[] map = int[numberOfItems, capacity];
for (int j=0; j<capacity; j++) {
map[0, j] = 0;
}
for (int i=0; i<numberOfItems; i++) {
for (int j=0; j<capacity; j++) {
if (j < w[i]) {
map[i, j] = map[i-1, j] // 1 up value
} else {
map[i, j] = max(
map[i-1, j], // this value
values[i] + map[i-1, j-wight[i, j]]) // this + 1 up level without weight
}
}
}
return map;
}Find the content
Modify the program and memorize which items are picked
List<Integer> find(int[] values, int[] weights, int numberOfItems, int capacity) {
boolean[][] keep = boolean[numberOfItems][capacity];
int[][] map = int[numberOfItems][capacity];
for (int j=0; j<capacity; j++) {
map[0, j] = 0;
}
for (int i=0; i<numberOfItems; i++) {
for (int j=0; j<capacity; j++) {
if (j < w[i]) {
map[i, j] = map[i-1, j] // 1 up value
keep[i, j] = false
} else {
int oneUpValue = map[i-1, j]; // 1 up value
int thisValue = values[i] + map[i-1, j-wight[i, j]]) // this + 1 up level without weight
map[i, j] = max(oneUpValue, thisValue);
if (oneUpValue > thisValue) {
keep[i, j] = false;
} else {
keep[i, j] = true;
}
}
}
}
List<Integer> result = ArrayList<>()
int weightLeft = capacity
for (int i=numberOfItems-1, i>=0; i--) {
if (keep[i, weightLeft] == true) {
result.add(i);
weightLeft =- wights[i];
}
if (weightLeft<=0) {
break;
}
}
return result;
}
