e****e
发帖数: 418 | 1 The idea is to explore all the combinations of weights array by masking and
bit shifting.
i.e. v1=5 w1=3, v2=3 w2=2, v3=4 w3=1, we form the two arrays as follows:
values[5, 3, 4], weights[3, 2, 1], W = 5.
for weights array[3, 2, 1], we want the all subsets of the elements.
such as:
[](no element)
[1]
[2]
[3]
[1 2]
[1 3]
[2 3]
[1 2 3]
We can get this subsets by masking bit by bit if we think of the array
bitwise.
[3 2 1]
0 0 0 -> (no element)
0 0 1 -> [1]
0 1 0 -> [2]
1 0 0 -> [3]
1 0 1 -> [1 3]
... ..
The code is simple. Here it is. Any suggestion is welcome.
public int knapsack01BruteForce(int[] values, int[] weights, int W) {
int numOfCombinations = (int) Math.pow( 2, weights.length );
int maxValueSum = Integer.MIN_VALUE;
for ( int i = 0; i < numOfCombinations; i++ ) {
int mask = i;
int weightSum = 0;
int valueSum = 0;
for ( int j = 0; j < weights.length; j++ ) {
int isIncluded = mask & 1; // isInclude is 0 or 1.
weightSum += weights[j] * isIncluded;
valueSum += values[j] * isIncluded;
mask >>= 1;
}
if ( weightSum <= W && valueSum > maxValueSum)
maxValueSum = valueSum;
}
return maxValueSum;
} |
|
