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