1. Problem Description (knapsack problem, 背包问题)
For a knapsack, you can put items in it with the maximum weight s. Now there exist n items, their weight is w1, w2, ..., wn, respectively and assume wi (1 i n) are all positive integers, which are put in a list w. You can define a recursive boolean function knap(s0, n0), if the selected n0 items are put into the knapsack and the total weight is exactly equal to s0, the function returns true, and outputs a set of the weight for selected items. Otherwise, it returns false.
Suppose s is 20 kg, n is 8 items, and the weight (kg) is a set of generated and non-repeated random positive integers between 1 and 25, such as 13, 8, 6, 2, 25, 19, 20, 1. Please design an algorithm to resolve this problem and then implement it by Python.
For example, a possible output is shown as follows:
s = 20
w = [13, 8, 6, 2, 25, 19, 20, 1]
There is a solution:
20=19+1
or
s = 20
w = [24, 17, 23, 8, 11, 15, 16, 25]
There is no solution.
Hint:
This problem can be recursively defined as follows:
true
if s0
= 0
successful
false
if s0
< 0
unsuccessful
knap(s0, n0) =
false
if s0
> 0 and n0 ≤ 0 unsuccessful
knap(s0, n0 - 1)
exclusive of wn in selected items
knap(s0 −, n0- 1) inclusive of wn in selected items
The first three lines in the above definition are boundary conditions (i.e. base case). The first line means that we don't put any item in the knapsack. The second line denotes that it is impossible that the total weight is less than zero. The third line indicates that if we don't put any item in the knapsack, the total weight cannot be greater than zero. Therefore, the definition is deterministic, because recursive procedure is executed each time: n0 minus 1, s0 minus wn possibly. Until s0 is less than 0 or n0 is equal to 0, we can use the boundary conditions to determine the final value. Note that it is possible that the final output result about weight of each item is not unique.
We use black-box test for this problem. That is to say, we observe three sets of output for different weight set. Then we check whether the output result is correct.
Submit your Experimental Report and Source Code
