The 0-1 Knapsack Problem (AKA The Discrete Knapsack Problem) is a famous problem solvable by dynamic-programming. In this article, I describe the problem, the most common algorithm used to solve it and then provide a sample implementation in C.

If you’ve never heard of the Knapsack Problems before, it will help to read this previous post.

#### The Problem

The Discrete (0-1) Knapsack Problem usually sounds like this:

Little Red Riding Hood wants to bring grandma a basket of goodies. She has an unlimited supply of

ntypes of sweets each weightingc[i]and having the nutritional value ofv[i]. Her basket can hold at mostWkilograms of sweets.Given

n,c,vandW, figure out which sweets and how many to take so that the nutritional value in maximal.

So, for this input:

`n = 3`

c = {8, 6, 4}

v = {16, 10, 7}

W = 10

LRRH should take one of *3* and one of *2*, amassing *17* nutritional points.

You’re usually dealling with a knapsack problem when you’re give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. **You have got the Discrete Knapsack Problem** when you can only take **the whole object or none at all** and you have an **unlimited supply of objects**.

#### The Algorithm

This is a dynamic-programming algorithm.

The idea is to first calculate the maximum benefit for weight *x* and only after that to calculate the maximum benefit for *x+1*. So, on the whole, you first calculate the maximum benefit for *1*, then for *2*, then for *3*, …, then for *W-1* and, finally, for *W*. I store the maximum benefits in an array named *a*.

Start with *a[0] = 0*. Then for every *a* between *1 … W* use the formula:

`a[i] = max{v`

_{j} + a(i − c_{j}) | c_{j} ≤ i }

The basic idea is that to reach weight *x*, you have to add an object of weight *w* to a previous maximum benefit. More specifically, you have to add *w* to *x – w*. Now, there will probably be several ways to reach weight *x*, so you have to choose the one that maximises the benefit. That’s what the max is for.

Basically, the formula says: “To calculate the benefit of weight *x*, take every object (value: *v*; weight: *w*) and see if the benefit for *x – w* plus *v* is greater than the current benefit for *x*. If so, change it.”

So, for the example, the programme would output (and do) this:

`Weight 0; Benefit: 0; Can't reach this exact weight.`

Weight 1; Benefit: 0; Can't reach this exact weight.

Weight 2; Benefit: 0; Can't reach this exact weight.

Weight 3; Benefit: 0; Can't reach this exact weight.

Weight 4; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 0.

Weight 5; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 1.

Weight 6; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 0.

Weight 7; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 1.

Weight 8; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 0.

Weight 9; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 1.

Weight 10; Benefit: 17; To reach this weight I added object 2 (10$ 6Kg) to weight 4.

#### The Programme

This programme runs in pseudo-plynominal time **O(n * W)**. i.e. Slow as hell for large very values of *W*. Also because it holds to arrays of at least length *W*, it’s also horribly memory inefficient. Unfortunately, there’s not much you can do.

Here’s the code in C (knapsack10.c):

#include <stdio.h> #define MAXWEIGHT 100 int n = 3; /* The number of objects */ int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what YOU PAY to take the object */ int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e. what YOU GET for taking the object */ int W = 10; /* The maximum weight you can take */ void fill_sack() { int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained using at most i weight */ int last_added[MAXWEIGHT]; /* I use this to calculate which object were added */ int i, j; int aux; for (i = 0; i <= W; ++i) { a[i] = 0; last_added[i] = -1; } a[0] = 0; for (i = 1; i <= W; ++i) for (j = 0; j < n; ++j) if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) { a[i] = a[i - c[j]] + v[j]; last_added[i] = j; } for (i = 0; i <= W; ++i) if (last_added[i] != -1) printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]); else printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i); printf("---\n"); aux = W; while ((aux > 0) && (last_added[aux] != -1)) { printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]); aux -= c[last_added[aux]]; } printf("Total value added: %d$\n", a[W]); } int main(int argc, char *argv[]) { fill_sack(); return 0; }

That’s it. Good luck. Always open to comments.

2007-11-20 at 21:11

[…] scvalex added an interesting post on The 0-1 Knapsack Problem […]

2007-11-21 at 7:56

[…] here for full story Der Beitrag wurde am Tuesday, den 20. November 2007 um 11:14 Uhr […]

2008-08-05 at 10:45

its good program, but it will be best if we can input the elemnts arry at first of program, so can you modify the program so we can input the array as we wish!

2008-11-10 at 7:47

oh thank u

2008-11-10 at 20:20

The code is great

Thanx

2009-03-07 at 12:43

Yelo, can somebody modify the programe code that you can enter the cost and the value of parts and the maximum weight you can take??

It would be great, when it,s possible please send it by mail i would be very grateful:}

greeting Miro

2009-03-07 at 12:44

Here is my mail:) misq51@o2.pl

2009-03-18 at 4:25

is there bug in the program?

I tried to modify the value of c and v, into, let say:

c[]={3,4,5}

v[]={5,7,8}

w remain 10

from logic, we can say the max benefit is 15, but the program return 17…

2009-07-09 at 19:22

The max benefit is 17.

If you take 2 of 1, and 1 of 2.

Then you have weight

3, 3, 4 = 10, and value

5, 5, 7 = 17

2009-03-18 at 4:53

I guess I found out the reason.

during the if(c[j]<=1 …. ), you did not check if the item reuse.

maybe your problem is different from mine, your item can reuse, my problem cant reuse the item.

2009-03-20 at 19:19

how to check it?? that the item was reuse?

2009-03-20 at 19:54

For example, to reach weight 3, I added item 1; to reach weight 6, I added item 1 again… that’s the problem.

To prevent it from reuse, I added a table to record down, if the item was used for a particular weight, put as 1, else 0.

2009-03-21 at 13:02

can you write this part of the code? and the place were you must add it? thx

2009-03-24 at 14:24

Vhanded can you send me the modified program (c code) on my e-mail?? I would be very grateful :) it’s very important here is my mail: misq51@o2.pl

2009-03-31 at 10:40

//The code that I modified is here:

#include

#define MAXWEIGHT 100

int n = 5;

int c[]={2,4,3,5,7}; //cost aka weight

int v[]={3,7,9,8,4}; //value aka benefit

int W=15; //maximum weight can take(bag size)

int main()

{

int table[W][n];

for(int i=0; i<=W; i++)

{

for(int j=0; j<n; j++)

{

table[i][j]=0;

}

}

int a[W]; //this hold the maximum value that can can be obtained using at most i weight

for(int i=0; i<=W; i++)

{

a[i]=0;

}

for(int i=1; i<=W; ++i)

{

for(int j=0; j<n; ++j)

{

if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)

//c[j]<=i, to allow only if selected weight bucket is less than i

//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.

//table[i-c[j]][j]!=1 is to prevent the items reuse.

{

for(int k=0; k=a[i])

{

table[i][j]=1;

}

a[i]=newTotalBenefit;

}

}

}

printf(“\t”);

for(int i=0; i<n; i++)

{

printf(“%d “,i);

}

printf(“\n”);

for(int i=0; i<=W; i++)

{

printf(“%d\t”, i);

for(int j=0; j<n; j++)

{

printf(“%d “,table[i][j]);

}

printf(“\n”);

}

printf(“\nmax benefit = %d”, a[W]);

}

//hope it helps.

2009-04-18 at 0:12

i am new to the knapsack problem

but it looks like that the lrrh problem described is an unbound knapsack problem.

2009-04-18 at 5:34

yup, it is. The solution I posted up is bounded.

2009-09-28 at 6:08

its cool thank you

2009-09-28 at 6:11

thx you its good

2009-11-04 at 17:47

Thank U so very much .. this post was very helpful in my studies …

2009-11-30 at 9:41

It was very much helpful

Thanks a lot!

2009-12-20 at 10:34

thank you so much..:D

2010-02-04 at 9:29

thanX….nice work….v got A+

2010-02-04 at 9:33

dude ur code had a bug…so i modifyd it….:)

#include

#define MAXWEIGHT 100

int n = 5;

int c[]={2,4,3,5,7}; //cost aka weight

int v[]={3,7,9,8,4}; //value aka benefit

int W=15; //maximum weight can take(bag size)

int main()

{

int table[W][n];

for(int i=0; i<=W; i++)

{

for(int j=0; j<n; j++)

{

table[i][j]=0;

}

}

int a[W]; //this hold the maximum value that can can be obtained using at most i weight

for(int i=0; i<=W; i++)

{

a[i]=0;

}

for(int i=1; i<=W; ++i)

{

for(int j=0; j<n; ++j)

{

if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)

//c[j]<=i, to allow only if selected weight bucket is less than i

//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.

//table[i-c[j]][j]!=1 is to prevent the items reuse.

{

for(int k=0; k=a[i])

{

table[i][j]=1;

}

a[i]=newTotalBenefit;

}

}

}

printf(“\t”);

for(int i=0; i<n; i++)

{

printf(“%d “,i);

}

printf(“\n”);

for(int i=0; i<=W; i++)

{

printf(“%d\t”, i);

for(int j=0; j<n; j++)

{

printf(“%d “,table[i][j]);

}

printf(“\n”);

}

printf(“\nmax benefit = %d”, a[W]);

}

//hope it helps.

2010-02-04 at 9:33

dude ur code had a bug…so i modifyd it….:)

#include

#define MAXWEIGHT 10

int n = 5;

int c[]={2,4,3,5,7}; //cost aka weight

int v[]={3,7,9,8,4}; //value aka benefit

int W=15; //maximum weight can take(bag size)

int main()

{

int table[W][n];

for(int i=0; i<=W; i++)

{

for(int j=0; j<n; j++)

{

table[i][j]=0;

}

}

int a[W]; //this hold the maximum value that can can be obtained using at most i weight

for(int i=0; i<=W; i++)

{

a[i]=0;

}

for(int i=1; i<=W; ++i)

{

for(int j=0; j<n; ++j)

{

if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)

//c[j]<=i, to allow only if selected weight bucket is less than i

//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.

//table[i-c[j]][j]!=1 is to prevent the items reuse.

{

for(int k=0; k=a[i])

{

table[i][j]=1;

}

a[i]=newTotalBenefit;

}

}

}

printf(“\t”);

for(int i=0; i<n; i++)

{

printf(“%d “,i);

}

printf(“\n”);

for(int i=0; i<=W; i++)

{

printf(“%d\t”, i);

for(int j=0; j<n; j++)

{

printf(“%d “,table[i][j]);

}

printf(“\n”);

}

printf(“\nmax benefit = %d”, a[W]);

}

//hope it helps.

2010-02-04 at 9:35

hey bro..!!!!!!!!

WASSUP???

i didnt understnd ur code man….

plzzzz help…:(

m screwd..:(

2010-02-04 at 9:39

i totaly agree wit anish….

mahambro plz xplain me d code!!!!

2010-02-04 at 10:02

mambro hav u copied ma code…????:@

u cheater…:@

wat d hell u think u duin….???

tak cr…:):)

2010-02-04 at 10:04

actualy i knew dat code b4…

bt thanX 2 mambro…he z real champ….:)

god bles him..ull b a gud programer….:)

thanX again…

2010-02-04 at 10:09

thanX sarvesh…:)

it ws gr8 complemnt…:)

it tuk me yr’s for devising dat logic…:)

bt i think smitaa hav sum probz wid ma code…

n for ur info..i didnt copy ur code…

2010-02-04 at 10:25

Wat a bakwaas code……………

shame on u mahambro…………..

2010-03-01 at 19:40

can anyone explain to me, i am still don’t get this part:

for (i = 1; i <= W; ++i)

for (j = 0; j < n; ++j)

if ((c[j] <= i) &&

(a[i] < a[i – c[j]] + v[j]))

{

a[i] = a[i – c[j]] + v[j];

last_added[i] = j;

}

and why we must use max weight in this code?

it it will get bugged up when u use max weight more than 100?

thanks for the info

2010-03-03 at 14:22

thanks for the source code

2010-03-26 at 10:42

thanks guys; very few c/c++ codes actually have no errors.

I am also understanding it,. very well thank you.

garcias.

2010-06-28 at 3:09

Thanks for the explanation and the implementation, they were very useful; I had been looking for a practical explanation of dynamic programming to solve this problem.

It’s a good post, thanks!

2011-03-12 at 2:00

What you explained is NOT the 0-1 knapsack problem, it is the generic unbounded one. In 0-1 knapsack problem, you are constrained to exactly one or none objects of one kind. In the unbounded knapsack problem, you have an unlimited supply of items (just as you explained in the blog post).

2011-03-28 at 6:08

Hello,

Thank you very much for this explanatory post, specially the part where you explained the output. BTW, if you add a check on line 28 of your code, the algorithm can be modified for use with limited supplies.

Cheers,

Tomas

2011-05-16 at 17:01

Isn’t there a bug in the code that scvalex has posted??

in the part where u include “a[i-c[j]]”, the code assumes that the item having cost c[j] has already been included…what if it was not??

consider c={2,10,13…} and v={2,3,6…}

a[0] and a[1] will be 0, a[2]=2 with cost factor 2, and till a[9] all a[i]s will have cost factor 2 and a[i]=2

a[10]=3 with cost factor 10, and so will a[11], a[12]=5 with cost factor 12, a[13]=6 with cost factor 13… and finally, here’s the problem..

a[14]=a[14-c[j]]+v[j]=a[14-2]+a[2]=a[12]+a[2]

which implies that item having cost 2 is being included twice!!!(since a[12]=a[10]+a[2])… hence i think there is a flaw in the code

2011-05-16 at 17:18

Yes, the code is OK since the item can be included n times because it is the Discrete Knapsack Problem. If you want to limit the items, you’ll need to add an “if” to line 28 in which you check whether the item was already used.

2011-05-20 at 1:35

And what would that “if” be?

“last_added[i] != -1” ?

2011-05-20 at 2:33

If you’re going to add “j” then you can keep a list of j’s that have been added previously to make sure that you don’t go over a certain amount >= 1.

2011-05-20 at 2:59

Would you mind please writing this in the example code? I have tried everything and it doesn’t work.I need some help.

2011-05-20 at 4:27

Sorry that it’s in Basic, but here’s my loop with a check:

2011-10-16 at 21:57

0-1 Knapsack Problem using array

#include

#include

#include

void main()

{

int w[10]={0,5,4,6,3};

int v[10]={0,10,40,30,50};

int n=4,c=10;

int s[20][20];

int keep[20][20],k;

clrscr();

for(int a=0;a<c;a++)

s[0][a]=0;

for(int b=1;b<=n;b++)

{

for(a=0;a<c;a++)

{

if(w[b]s[b-1][a] )

{

s[b][a]=v[b]+s[b-1][a-w[b]];

keep[b][a]=1;

}

else

{

s[b][a]=s[b-1][a];

keep[b][a]=0;

}

}

}

cout<<"\n"; //print set of all possible max value

for(int d=0;d<=n;d++)

{

for(int g=0;g<c;g++)

{

cout<<s[d][g]<<"\t";

}

cout<<"\n";

}

cout<=1;y–)

{

if(keep[y][k-1]==1)

{

cout<<y<<" ";

k=k-w[y];

}

}

cout<<"}";

getch();

}

2014-07-15 at 21:42

If you would like to obtain a great deal from this

piece of writing then you have to apply such methods

to your won weblog.

2017-01-09 at 10:54

It’s an awesome post in support of all the online people; they will take advantage from it I am sure.