Help : 0/1 Knapsack Problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Help : 0/1 Knapsack Problem

Post by Chok » Tue Oct 18, 2005 6:39 pm

Hello all,
I've just learned(no so good) 0/1 knapsack. With help of this, we can generate the number of ways to make S with n elements. But i'm trying to modify it where we should use each element only once for a valid result. Sometimes i got wrong result. Please help me. How i correctly modify the general solution.
Generally we did, like 3 elements {1,2,3}, we can get the sum 5 by
{1,1,1,1,1} 1 use more than one times
{1,2,2} 2 use more than one times
{1,1,3} 1 use more than one times
{2,3}
... permutation should be ignore. cnt[5]=4
But i want only this -->
{2,3} , cnt[5]=1
Thanks in advance.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Tue Oct 18, 2005 10:11 pm

You might have got wrong answer for using a 1D array. In this case you may use a number more than once. Try using a 2D array.

Regards
Sanny

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Hi

Post by Chok » Tue Oct 18, 2005 11:04 pm

Hi Sanny,
Thankx for ur reply. Actually I'm not using 1D array, i used 2D array. I wrote it in my pre thread just make understand. By tha way My solution for the general case is

Code: Select all

void process(void)
{
	int i,j;

	for(i=0;i<100;i++)
		way[i][0] = 0;
	for(i=0;i<10;i++)
		way[0][i] = 1;

	for(i=1;i<100;i++)
	{
		for(j=1;j<10;j++)
		{
			way[i][j] = way[i][j-1];
			if(i-deno[j] >=0)
				way[i][j] += way[i-deno[j]][j];
		}
	}
	return;
}
How can i modify it ? Any hint ?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: Hi

Post by misof » Tue Oct 18, 2005 11:49 pm

Chok wrote:Hi Sanny,
Thankx for ur reply. Actually I'm not using 1D array, i used 2D array. I wrote it in my pre thread just make understand. By tha way My solution for the general case is

Code: Select all

void process(void)
{
	int i,j;

	for(i=0;i<100;i++)
		way[i][0] = 0;
	for(i=0;i<10;i++)
		way[0][i] = 1;

	for(i=1;i<100;i++)
	{
		for(j=1;j<10;j++)
		{
			way[i][j] = way[i][j-1];
			if(i-deno[j] >=0)
				way[i][j] += way[i-deno[j]][j];
		}
	}
	return;
}
How can i modify it ? Any hint ?
Just change the last j to j-1, i.e., obtain the sum (i-deno[j]) using the first j-1 elements only. BTW, there is a simple way of solving this task using a single 1D array :)

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Re: Hi

Post by Sanny » Wed Oct 19, 2005 9:35 am

misof wrote:BTW, there is a simple way of solving this task using a single 1D array :)
Looping down instead of up?

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Wed Oct 19, 2005 1:09 pm

Hi Misof and Sanny,
Thanks. Now its clear to me. But i'm interested to know how i do it with a 1D array? is this avoid permutation ? Thankx again.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Wed Oct 19, 2005 1:57 pm

Hi Misof,
I've something figure out. Now i want to remove repeatation and premutation, then ?

Code: Select all

int coin[3]={3,2,1};
int a[MAX+1];
v=3;
a[0]=1;
for(i=0;i<v;i++) 
{
	c=coin[i];
	for(j=c;j<=MAX;j++)
		a[j]+=a[j-c];
}
Thanks in advance.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Oct 19, 2005 3:31 pm

Chok wrote:Hi Misof,
I've something figure out. Now i want to remove repeatation and premutation, then ?

Code: Select all

int coin[3]={3,2,1};
int a[MAX+1];
v=3;
a[0]=1;
for(i=0;i<v;i++) 
{
	c=coin[i];
	for(j=c;j<=MAX;j++)
		a[j]+=a[j-c];
}
Thanks in advance.
This code does compute the answer if repeated using of the same element is possible. (Note that permutations are not counted separately, e.g. 1+2+2 is the same as 2+1+2.)

This is because the value a[j-c] is already a new value (i.e., updated in the current pass), and thus it contains the number of possibilities using the first i elements. If you reverse the direction for the j-cycle, the value a[j-c] will be the old value, i.e., the number of possibilities for sum j-c using first i-1 elements only.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok » Wed Oct 19, 2005 4:37 pm

Hi misof,
Thanks again for ur reply. Now i'm trying to understand it and implement it. Thanks again.

Post Reply

Return to “Algorithms”