quentions about a knapsack problem

[frk_styc]

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:

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;
			}
		}
	}
}

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?

[nibbler]

Try this, it is O(N*M)

Code: Select all

#include <cstdio>
#include <vector>
using namespace std;

int main() {
	int N,M,cnt=0;
	scanf ("%d %d",&N,&M);
	vector <int> weight(N),amount(N), V(M+1), R(M+1);
	for (int i=0;i<N;i++) 
		 scanf ("%d %d",&weight[i],&amount[i]);

	V[0]=1;
	for (int i=0;i<N;i++) {
		int w=weight[i],a=amount[i];
		for (int j=0;j<=M;j++) R[j]=0;
		
		for (int j=w;j<=M;j++) 
			if (V[j]==0)
				if (V[j-w]==1 && R[j-w]<a) {
					V[j]=1;
					R[j]=R[j-w]+1;
					cnt++;
				}
	}
	
		printf ("\n%d\n",cnt);
	return 0;
}

DP: in N rounds, you put only one object type. W is wieght, and A is total amount of the current object. For each size in knapsack from 1...M, you store what is the minimal number of current objects to achieve it ( if you achieved it before curr object then that number is 0 ). Then you can fill knapsack[ j ] if you could fill knapsack[ j - W ] with less then A objects.

[frk_styc]

Thanks!
I've found the key to the problem. First, the division in the inner loop of my code takes too much time. It's completely unnecessarily to do such a division. Second, counting can be done during the process of DP, this saves an additional loop and provides the possibility to end the outer loop as soon as possible. But the biggest problem of my old code is that it's buggy. My new code runs at 1.7s and have got accepted.

Try this, it is O(N*M)

Code: Select all

#include <cstdio>
#include <vector>
using namespace std;

int main() {
	int N,M,cnt=0;
	scanf ("%d %d",&N,&M);
	vector <int> weight(N),amount(N), V(M+1), R(M+1);
	for (int i=0;i<N;i++) 
		 scanf ("%d %d",&weight[i],&amount[i]);

	V[0]=1;
	for (int i=0;i<N;i++) {
		int w=weight[i],a=amount[i];
		for (int j=0;j<=M;j++) R[j]=0;
		
		for (int j=w;j<=M;j++) 
			if (V[j]==0)
				if (V[j-w]==1 && R[j-w]<a) {
					V[j]=1;
					R[j]=R[j-w]+1;
					cnt++;
				}
	}
	
		printf ("\n%d\n",cnt);
	return 0;
}

DP: in N rounds, you put only one object type. W is wieght, and A is total amount of the current object. For each size in knapsack from 1...M, you store what is the minimal number of current objects to achieve it ( if you achieved it before curr object then that number is 0 ). Then you can fill knapsack[ j ] if you could fill knapsack[ j - W ] with less then A objects.