Thread: Knapsack Problem

I'm sure putting "knapsack problem" into a search engine will tell you all you need to know.

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.

How can I get A[n] to increase like a binary counter so that it checks every possible combination of items??

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.

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

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.