Thread: need help with simple knapsack problem

  1. #1
    Registered User
    Join Date
    Dec 2001

    need help with simple knapsack problem

    Hey guys, ive been working on this program for a week and a half now for my independent study cs class, for anyone who doesnt know what the knapsack problem is heres how it goes: in a knapsack you have different weights, but with those weights you can arrange them in difffernt combinations to achieve a "goal" weight, if anyone can help me out with this id appreciate it heres what i have so far :

    #include <iostream.h>
    #include <lvp\string.h>
    #include <lvp\vector.h>

    void LoadData(/*int n,*/ int goal, vector <int> &KnapsackArr)
    //Pre: None
    //Post:Enters data into array, enters number for search

    // vector <int> KnapsackArr (n);
    int n=0;
    cout<<"Enter value (0=done) : ";

    while (KnapsackArr[n]!=0)
    cout<<"Enter value (0=done) : ";

    cout<<"Enter goal (0=done) : ";

    void FindCombo(int &n, int &goal, int newnum, vector <int> &KnapsackArr, vector <int> &UsedArr)
    //Pre:Array with values in array
    //Post:Returns combinations for number
    if (KnapsackArr[n]==goal)
    cout<<KnapsackArr[n]<<" ";
    /*else if (Knapsack[n]!=UsedArr[n])
    cout<<KnapsackArr[n]<<" "<<n;
    } */
    void DisplayResults(int &goal)

    if (goal!=0)
    cout<<"No Solution";

    int main ()
    int n, goal, newnum;
    vector <int> KnapsackArr(10);
    vector <int> UsedArr(10);
    LoadData(goal, KnapsackArr);
    FindCombo(n, goal, newnum, KnapsackArr, UsedArr);

    return (0);

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Is it ok to find just one solution, or do you need to find all of them? I posted a solution to this problem a few days ago, although I don't think it had this name.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A simple file I/O problem
    By eecoder in forum C Programming
    Replies: 10
    Last Post: 10-16-2010, 11:00 PM
  2. Simple Gets() problem
    By akira181 in forum C++ Programming
    Replies: 17
    Last Post: 05-25-2006, 03:28 AM
  3. Problem in simple code.
    By richdb in forum C Programming
    Replies: 6
    Last Post: 03-20-2006, 02:45 AM
  4. Problem in very simple code
    By richdb in forum C Programming
    Replies: 22
    Last Post: 01-14-2006, 09:10 PM
  5. Simple File I/O problem
    By Ignited in forum C++ Programming
    Replies: 3
    Last Post: 01-07-2006, 10:49 AM