### quentions about a knapsack problem

Posted:

**Sun Apr 17, 2005 5:37 pm**I'm now trying to solve a knapsack problem but find that an ordinary DP is too slow to handle it. A detailed description is: There are N<=100 types of objects whose values lie between 1 and 1000. To fill a knapsack of volume M<=100000, at most c_i<=1000 of the ith type can be selected. Calculate how many possible different sums>0 of values there are. For example, using two objects of value 1 and one object of value 4 to fill a knapsack of volume 5, all possible sums are 1, 2, 4 and 5 and therefore the answer is 4.

Following is my code:
This code turns out too slow. When I submitted it to an OJ, I could only get a TLE (time limit 3s). I tried reducing the times of the inner loop being executed by recording the current max sum. But this gave no improvement. I also tried other minor optimizations and the effect is also minor.

What major optimization can be done to the code? If that does not exist, how can the algorithm be improved? Should other data structures like heap be introduced?

Following is my code:

Code: Select all

```
p[0] = 1; //the table recording all possible sums
for(i = 0; i < N; i++)
{
int cv = obj[i].v; //value of object i
int cc = obj[i].c; //max number of object i
for(j = M - cv; j >= 0; j--)
{
if(p[j] != 0 && p[j + cv] == 0)
{
int v;
int c = (M - j) / cv;
if(c > cc)
{
c = cc;
}
v = j + cv;
for(k = 1; p[v] == 0 && k <= c; k++)
{
p[v] = 1;
v += cv;
}
}
}
}
```

What major optimization can be done to the code? If that does not exist, how can the algorithm be improved? Should other data structures like heap be introduced?