## Help : 0/1 Knapsack Problem

**Moderator:** Board moderators

### Help : 0/1 Knapsack Problem

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.

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.

### Hi

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
How can i modify it ? Any hint ?

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

### Re: Hi

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 arrayChok 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 isHow can i modify it ? Any hint ?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; }`

### Re: Hi

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

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

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.)Chok wrote:Hi Misof,

I've something figure out. Now i want to remove repeatation and premutation, then ?Thanks in advance.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]; }`

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.