Knapsack Problem

This is a discussion on Knapsack Problem within the C Programming forums, part of the General Programming Boards category; I want to work out the max value of items that can be placed in a bag under a weight ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    5

    Knapsack Problem

    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??

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,834
    I'm sure putting "knapsack problem" into a search engine will tell you all you need to know.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    5
    Believe me I've tried, just can't seem to get my head around this problem for some reason

  4. #4
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    This page offers a good explanation in semi-programmatical terms.
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. knapsack problem
    By fnfn in forum C++ Programming
    Replies: 1
    Last Post: 07-19-2007, 04:14 PM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  5. Multiple Knapsack Problem
    By polymeta in forum C Programming
    Replies: 3
    Last Post: 11-15-2001, 08:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21