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