Hi everyone, someone can help me with these exercise, they are from CP3, but I can't handle them
I'll really appreciate it if you could help me
Exercise 3.5.2.5: Suppose we add one more parameter to this classic 0-1 Knapsack problem.
Let Ki denote the number of copies of item i for use in the problem. Example: n = 2,
V = {100, 70}, W = {5, 4}, K = {2, 3}, S = 17 means that there are two copies of item 0
with weight 5 and value 100 and there are three copies of item 1 with weight 4 and value
70. The optimal solution for this example is to take one of item 0 and three of item 1, with
a total weight of 17 and total value 310. Solve new variant of the problem assuming that
1 ≤ n ≤ 500, 1 ≤ S ≤ 2000, n ≤ Sum(Ki) ≤ 40000! Hint: Every integer can be written as a
sum of powers of 2.
Exercise 3.5.2.6: The DP TSP solution shown in this section can still be slightly enhanced
to make it able to solve test case with n = 17 in contest environment. Show the required
minor change to make this possible! Hint: Consider symmetry!
Exercise 3.5.2.7: On top of the minor change asked in Exercise 3.5.2.5, what other
change(s) is/are needed to have a DP TSP solution that is able to handle n = 18 (or even
n = 19, but with much lesser number of test cases)?
About 3.5.2.5 , it's a classic trick, decompose ki into 2^0 , ... , 2^t , (ki — (2^(t+1) — 1)) (such that (2^(t+1) — 1) <= ki and t is maximum) and do Knapsack, since 2^(t+1) — 1 = 2^0 + .. + 2^t , we can create every number between 0 and 2^(t+1) — 1 (it's equivalent to write the number in base 2) and since we have ki — (2^(t+1) — 1) we can create the numbers between 2^(t+1) and ki
wow, thanks, that is a really good trick