need help with simple knapsack problem

This is a discussion on need help with simple knapsack problem within the C++ Programming forums, part of the General Programming Boards category; Hey guys, ive been working on this program for a week and a half now for my independent study cs ...

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    3

    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) : ";
    cin>>KnapsackArr[n];

    while (KnapsackArr[n]!=0)
    {
    n++;
    cout<<"Enter value (0=done) : ";
    cin>>KnapsackArr[n];
    }

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

    }
    //------------------------------------------------------------------------------
    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]<<" ";
    KnapsackArr[n]=UsedArr[n];
    }
    /*else if (Knapsack[n]!=UsedArr[n])
    {
    goal-KnapsackArr[n]=newnum;
    cout<<KnapsackArr[n]<<" "<<n;
    } */
    }
    //------------------------------------------------------------------------------
    void DisplayResults(int &goal)
    {

    if (goal!=0)
    cout<<goal;
    else
    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);
    DisplayResults(goal);

    return (0);
    }

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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-17-2010, 12:00 AM
  2. Simple Gets() problem
    By akira181 in forum C++ Programming
    Replies: 17
    Last Post: 05-25-2006, 04: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

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