0/1 Knapsack and its related UVa problems
Definition
There are n weights, each of which has a value, denoted as
w1, w2, ... wn, and
v1, v2, ... vn,
The problem is to find a subset of w_i, which total weight
does not exceed W, and the sum of their respective values
has the maximum value.
That is
Condition: w_i1 + w_i2 + .... w_ik <= W
maximum: v_i1 + v_i2 + .... v_ik
For example:
w[] = 1 3 4
v[] = 7 2 6
We have eight subsets:
w1 w2 w3
----------
0 0 0 => ∅, totalw = 0, totalv = 0
1 0 0 => {w1}, totalw = 1, totalv = 7
0 1 0 => {w2}, totalw = 3, totalv = 2
1 1 0 => {w1, w2}, totalw = 4, totalv = 9
0 0 1 => {w3}, totalw = 4, totalv = 6
1 0 1 => {w1, w3}, totalw = 5, totalv = 13
0 1 1 => {w2, w3}, totalw = 7, totalv = 8
1 1 1 => {w1, w2, w3},totalw = 8, totalv = 15
If W = 7, we have maximum value = 13.
If W = 4, we have maximum value = 9. (formed with {w3} or {w1,w2})
Generation of all subset
The above process of generating all subsets can be explained step by step
as follows.
Initially, we have only subset, ∅.
w1 w2 w3
----------
0 0 0 => ∅ totalw = 0, totalv = 0
Then we try to insert w1 and get
w1 w2 w3
----------
1 0 0 => {w1}, totalw = 1, totalv = 7
Combined with the original ∅, we have
w1 w2 w3
----------
0 0 0 => ∅, totalw = 0, totalv = 0
1 0 0 => {w1}, totalw = 1, totalv = 7
Now inserting w2 or not inserting w2 gives
w1 w2 w3
----------
0 0 0 => ∅, totalw = 0, totalv = 0
1 0 0 => {w1}, totalw = 1, totalv = 7
0 1 0 => {w2}, totalw = 3, totalv = 2
1 1 0 => {w1, w2}, totalw = 4, totalv = 9
Finally, we handle w3 and get the table as shown above.
Generation of all sums
Of course, we are not interested in members of a subset but in
the total weight and total value the subset gives.
So the above process can be abbreviated as follows.
Initially
w1 w2 w3 possible [weight,value]
---------- -------------------------
0 0 0 => [0,0]
Try w1
w1 w2 w3 possible [weight,value]
---------- -------------------------
0 0 0 => [0,0] original
1 0 0 => [1,7] [0,0] + [w1,v1] = [1,7]
The original and the new part are combined
w1 w2 w3 possible [weight,value]
---------- -------------------------
0/1 0 0 => [0,0], [1,7]
Try w2
w1 w2 w3 possible [weight,value]
---------- -------------------------
0/1 0 0 => [0,0], [1,7] original
0/1 1 0 => [3,2], [4,9] original + [3,2]
Combined.
w1 w2 w3 possible [weight,value]
---------- -------------------------
0/1 0/1 0 => [0,0], [1,7], [3,2], [4,9]
Try w3
w1 w2 w3 possible [weight,value]
---------- -------------------------
0/1 0/1 0 => [0,0], [1,7], [3,2], [4,9] original
0/1 0/1 1 => [4,6], [5,12], [7,8], [8,15] original + [4,6]
Combined
w1 w2 w3 possible [weight,value]
---------- -------------------------
0/1 0/1 0/1 => [0,0], [1,7], [3,2], [4,9], [5,12], [7,8], [8,15]
Since we try to find the maximum value, when combing [4,6] and [4,9],
we just choose the bigger one.
Solved by Dynamic Programming
The above process gives the following pseudo code:
Let P = possible pairs, N = new pairs
P = ∅
for i=1,2,....n
N = P + [wi, vi]
P = P + N;
try to find in P the pair which wi<=W and has the maximum vi
If all wi >= 0, the new sum of weight is not less than the original.
So when got a wi > W, it is not necessary to put the pair in P.
So the number of pairs does not exceed W and the time complexity of
the code is simply O(nW). If W = 2n, the time is still exponential.
But in many cases, the W is much less than 2n.
So solving the problem in polynomial time is possible.
To encode the program, We use an array to store all possible pairs.
That is, sum[w]=v means [w,v].
sum[0] = 0; got[0] = true
for i=1,2,...W
sum[i] = 0; got[i] = false
for i=1,2,...n
for cw = W, W-1, W-2, .....0
if(not got[cw]) continue
sum[cw + w[i]] = max(sum[cw + w[i]], cw + w[i])
got[cw + w[j]] = true
maxv = -1
for i=0,1,2....W
if got(i) and sum[i] > maxv
maxv = sum[i]
Note the sum is tried from W, W-1, .. to 0. The pseudo code has two
phases to run: generation of new pairs, combination of two parts.
The code shown above does these two things in single step.
If the sum is tried from 0,1,...W, it is possible some w[i] are
added more than once..
For example:
The original sum[] is
i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 0 2 5
Add [2,5]. The new part is
i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 5 7 10
Combined
i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 0 2 5 7 10
If tried from W to 0, the answer is the same as above.
If tried from 0 to W,
cw=0 i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 0 2 5 5
cw=1 i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 0 2 5 7
cw=2 i | 0 1 2 3 4 5 6 7
-----+-----------------------
sum[]| 0 2 5 7 12 <---- [2,7] added twice
UVa 10032: Tug of War
Description:
The problem asks you to split w1,w2,....wn into two parts
such that
a) the difference between sums of parts is minimal.
b) the difference between the numbers of wi in these two parts
should be 0 (n is even) or 1 (n is odd).
Solution:
You have to find a subset which sum of weight is as close as
possible to the half of the total weights. So it is clearly a 0/1
knapsack problem. But what is the value?
For a set, figuring out of its cardinality is easy if we have kept
the members. But it is not true. For a set, the previous pseudo code
only keeps its sum and value. So the challenge of this problem is
to determine the cardinality of a set.
For a sum=101, we want to know if 101 can be formed with some weights,
and how many weight are involved in such combinations.
To do this, we accommodate each sum a set of counts.
For example, if sum[29] = {4,6,8}, it means 29 can be formed
with 4 weights, 6 weights, or 8 weights.
Now if a new weight wi=2, 29 + 2 = 31, sum[31] should
include {5,7,9} as 31 can be formed with 5 weights (4 for 29, 1 for 2),
7 weights (6 for 29, 1 for 2) and 9 weights.
Note sum[31] may contain other counts so sum[31] = sum[31] ∪ {5,7,9}.
For another example, w1, w2, w3, w4 = 1 2 2 1, we have
sum[0] = {0}
sum[1] = {1} w1, w4
sum[2] = {1,2} w1+w4, w2, w3
sum[3] = {2} w1+w2, w2+w4,... all cases use 2 weights
sum[4] = {2,3} w2+w4, w1+w2+w4
sum[5] = {3} w2+w3+w4
sum[6] = {4} w1+w2+w3+w4
Now adding w5 = 1, the new part is
sum[0] = {0}
sum[1] = {1} sum[0] + 1 {0} --> {1}
sum[2] = {2} sum[1] + 1 {0} --> {1}
sum[3] = {2,3} sum[2] + 1: {1,2} --> {2,3}
sum[4] = {3} sum[3] + 1: {2} --> {3}
sum[5] = {3,4} sum[4] + 1: {2,3} --> {3,4}
sum[6] = {4} sum[5] + 1
sum[7] = {5}
Combine them.
sum[0] = {0}
sum[1] = {1}
sum[2] = {1,2} {1,2} ∪ {2} = {1,2}
sum[3] = {2,3} {2} ∪ {2,3} = {2,3}
sum[4] = {2,3} {2,3} ∪ {3} = {2,3}
sum[5] = {3,4} {3} ∪ {3,4} = {3,4}
sum[6] = {4}
sum[7] = {5}
Now the difficulty is how to implement a set.
A set is commonly implemented with a bitmask.
Since N≤100, N/2≤50, at most 50 bits are to be handled, so
a long long is enough.
A {4,6,8} is represented with a long long as
bitmask 0000 0001 0101 0000
--------------------------------
position 5432 1098 7654 3210
1111 1
So to get {5,7,9} from {4,6,8} is just to shift it left one bit.
bitmask 0000 0010 1010 0000
--------------------------------
position 5432 1098 7654 3210
1111 1
With the above bitmask setup, the code for 'tug of war' should be like:
totalw = sum of w1, w2 , ...
halfw = totalw/2
clear C[0], C[1], .... C[ halfw ], C[i] is the bitmask for sum[i]
C[0] = 1
for i=1,2,3....n
for cw=halfw,.....0
C[cw+ wi] |= C[cw] << 1
find the answer
UVa 711: Dividing up
Description:
There are marbles with values 1,2,3,4,5,6. Try to split the marbles
into two parts such that the sums of values of two parts are equal.
For example
value of marble | 1 2 3 4 5 6
----------------+-----------------------
count | 4 0 0 0 0 3
Total values = 1*4 + 6*4 = 26. So the target is 26/2 = 13.
Because 13 = 1*1 + 2*6, the input marbles is dividable.
Solution:
This is clearly a bounded knapsack problem. We have six weights but
counts of weights are not 1. If the input is
value of marble | 1 2 3 4 5 6
----------------+-----------------------
count | 4 0 1 3 2 10
The balls with value 6 can be viewed as individual 10 6's.
Other values can be treated similarly. So the input is transformed to
1 1 1 1 3 4 4 4 5 5 6 6 6 6 6 6 6 6 6 6.
And now it is ready for 0/1 knapsack with 20 weights.
Easy! But the number of balls can be as large as 20000 and the W can be
as large as 30000. 20000 * 60000 = 6 * 108, too big to compute.
The 6 can be used 0 times, 1 times, 2 times,... 10 times.
If sum = 27 is to be formed with 1 3's and 4 6's, the previous
transformation makes dp compute sum[27] with 0+3+6+6+6+6.
How about 0+3+6*4?
Since 10 = 1 + 2 + 4 + 3, we can decompose 10 6's into
1*6=6, 2*6=12, 4*6=24, 3*6=18, total 4 weights.
Now every possible mutiples of 6 can be combined with the
previous 4 weights. Other values of marbles can be treated similarly.
If there are N marble, such binary decomposition produce O(log N) weights.
The W is at most 6*N/2 = 3N. The time complexity of this problem is
thus O(N logN). Feasible!