Printable View
I want to work out the max value of items that can be placed in a bag under a weight constraint C. I have the values and weights of the items stored in two arrays and i want to make another array which will hold 0 or 1 corresponding to whether the item is included or not (call it A[n]). How can I get A[n] to increase like a binary counter so that it checks every possible combination of items??
I'm sure putting "knapsack problem" into a search engine will tell you all you need to know.
Believe me I've tried, just can't seem to get my head around this problem for some reason
This page offers a good explanation in semi-programmatical terms.
Guys... his question was very specific. He wasn't asking for info about the knapsack problem.
There's two ways to go about this. First off, what you are looking for, is a counting method. I'll assume that A[n] is an array of ints. The following code performs the kind of incremental counting you are looking for.Quote:
How can I get A[n] to increase like a binary counter so that it checks every possible combination of items??
A much more elegant way to go about solving the knapsack problem would be to, instead of using a counting array, use a recursive function to perform the solution. There is a direct analogue between counting and basic tree recursion.Code:#include <stdio.h>
void zeroarr (int * array, size_t size) {
int i;
for (i = 0; i < size; ++i) {
array[i] = 0;
}
return;
}
void printarr (int * array, size_t size) {
int i;
for (i = 0; i < size; ++i) {
printf ("%d", array[i]);
}
printf ("\n");
return;
}
// Return 1 if overflow
// This is what you want.
int incrarr (int * arr, size_t size) {
int i;
for (i = 0; i < size; ++i) {
if (arr[i] == 1) {
// 1 encountered. Set to 0 and increment next value
arr[i] = 0;
}
else {
// 0 encountered. Set to 1, and stop incrementing
arr[i] = 1;
break;
}
}
// Detect overflow
return i == size;
}
int main (void) {
int a[8];
zeroarr(a, 8);
for (;;) {
printarr(a, 8);
if (incrarr(a, 8))
break;
}
}