AaronSwartz's blog

By AaronSwartz, history, 23 months ago, In English,

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)?

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it