Reputation: 590
So, it's basically the same problem as the 0/1 knapsack problem: n items, each having a weight w_i, and a value v_i, maximise the value of all items but keeping the total weight less than W. However, their is a slight twist: The amount of items in the knapsack need to be even. The result should then be the total value of all the items in the knapsack.
I tried the following: I use two DP tables of size (n+1) x (W+1), DP_odd and DP_even. I filled them according to:
DP_even[i][j] = max( DP_even[i-1][j] || DP_odd[i-1][j - weights[i]] + values[i] )
DP_odd[i][j] = max( DP_odd[i-1][j] || DP_even[i-1][j - weights[i]] + values[i] )
The result (the total value) should then be in DP_even[n][W]. However, the result is incorrect. I just get two equal DP tables.
Here is the implementation:
public class KnapSackEven {
public static void main(String[] args) {
int[] weights = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
int[] values = new int[] {2, 1, 3, 15, 3, 5, 9, 4}};
int n = weights.length;
int W = 10;
int[][] DP_odd = new int[n+1][W+1];
int[][] DP_even = new int[n+1][W+1];
for(int i = 0; i < n+1; i++) {
for(int j = 0; j < W+1; j++) {
if(i == 0 || j == 0) {
DP_odd[i][j] = 0;
DP_even[i][j] = 0;
} else if(j - weights[i-1] >= 0) {
DP_even[i][j] = Math.max(DP_even[i-1][j], DP_odd[i-1][j - weights[i-1]] + values[i-1]);
DP_odd[i][j] = Math.max(DP_odd[i-1][j], DP_even[i-1][j - weights[i-1]] + values[i-1]);
} else {
DP_even[i][j] = DP_even[i-1][j];
DP_odd[i][j] = DP_odd[i-1][j];
}
}
}
System.out.println("Result: " + DP_even[n][W]);
}
}
Result: 23
However, the result should be 20. Because the total value 23 can't consist of an even amount of items. It took the the items weigths[2], weights[3] and weights[5], but that's not an even amount... It should have taken weights[3] and weights[5].
For everyone that wants to see, here are the DP tables: (the first column is values[i], the second column is weights[i]:
DP_even:
0 0 0 0 0 0 0 0 0 0 0 0 0
2 4 0 0 0 0 2 2 2 2 2 2 2
1 3 0 0 0 1 2 2 2 3 3 3 3
3 3 0 0 0 3 3 3 4 5 5 5 6
15 5 0 0 0 3 3 15 15 15 18 18 18
3 1 0 3 3 3 6 15 18 18 18 21 21
5 2 0 3 5 8 8 15 18 20 23 23 23
9 7 0 3 5 8 8 15 18 20 23 23 23
4 12 0 3 5 8 8 15 18 20 23 23 23
DP_odd:
0 0 0 0 0 0 0 0 0 0 0 0 0
2 4 0 0 0 0 2 2 2 2 2 2 2
1 3 0 0 0 1 2 2 2 3 3 3 3
3 3 0 0 0 3 3 3 4 5 5 5 6
15 5 0 0 0 3 3 15 15 15 18 18 18
3 1 0 3 3 3 6 15 18 18 18 21 21
5 2 0 3 5 8 8 15 18 20 23 23 23
9 7 0 3 5 8 8 15 18 20 23 23 23
4 12 0 3 5 8 8 15 18 20 23 23 23
Backtracking gives the solution: weights[2], weighst[3] and weights[5] => total values 23.
Even though the method seems like it could work, it still doesn't.
Is there another way to solve this?
Upvotes: 1
Views: 762
Reputation: 18559
You can get a value of 20 by taking the 15 and the 5, so the result should be 20.
DP_odd[i][j] = 0
isn't right because 0 items is not odd. The way it is now is symmetrical with DP_even
so the result will be the same.
Instead, set DP_odd[0][0]
to a negative number and check for these negative numbers in the other sums and don't allow them to be used.
So something like:
public class KnapSackEven {
public static void main(String[] args) {
int[] weights = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
int[] values = new int[] {2, 1, 3, 15, 3, 5, 9, 4};
int n = weights.length;
int W = 10;
int[][] DP_odd = new int[n+1][W+1];
int[][] DP_even = new int[n+1][W+1];
for(int i = 0; i < n+1; i++) {
for(int j = 0; j < W+1; j++) {
DP_even[i][j] = -1;
DP_odd[i][j] = -1;
if(i == 0 || j == 0) {
DP_odd[i][j] = -1;
DP_even[i][j] = 0;
} else if(j - weights[i-1] >= 0) {
if(DP_odd[i-1][j - weights[i-1]] >= 0) {
DP_even[i][j] = Math.max(DP_even[i-1][j], DP_odd[i-1][j - weights[i-1]] + values[i-1]);
}
if(DP_even[i-1][j - weights[i-1]] >= 0) {
DP_odd[i][j] = Math.max(DP_odd[i-1][j], DP_even[i-1][j - weights[i-1]] + values[i-1]);
}
}
if(i > 0) {
DP_odd[i][j] = Math.max(DP_odd[i][j], DP_odd[i-1][j]);
DP_even[i][j] = Math.max(DP_even[i][j], DP_even[i-1][j]);
}
}
}
System.out.println("Result: " + DP_even[n][W]);
}
}
Upvotes: 2