UVa 624 CD

Problem: binary knapsack problem with integer size. In the description, the knapsack is a CD with length N and the items are songs with length l1, l2, ..., lk. All numbers are integer.

Size: the number of songs k is less than or equal to 20, but N is not limited.

Solution: let s[w] be boolean, true if there exists a solution with length w exactly, and let c[w, j] true if item j is chosen in the corresponding solution. Then mark the table from s[0] to s[N]:

1) s[0] = true, c[0, j] = false
2) for w from 1 to N
    for all j
       mark s[w+lj] true if s[w] true and c[w][j] false
       mark the corresponding c[w+lj][j] if s[w+lj] true

Then find the max w that s[w] true in the table. The general dynamic programming solution in Wikipedia also works.