DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

# The 0-1 Knapsack Problem In C

11.20.2007
| 49312 views |
```        This is a dynamic-programming algorithm implementation for solving the <a href="http://en.wikipedia.org/wiki/Knapsack_problem">the 0-1 Knapsack Problem</a> in C.

Further explanation is given <a href="http://compprog.wordpress.com/2007/11/20/the-0-1-knapsack-problem/">here</a>.

```
```#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
int i, j;
int aux;

for (i = 0; i <= W; ++i) {
a[i] = 0;
}

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

for (i = 0; i <= W; ++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)) {
}

`    `