-
October 8th, 2007, 06:23 PM
#1
please help with knapsack program
hello everyone, i am new to c++ and programming overall...just decided to try some things out..
i am currently trying to implement the knapsack problem....
this code works correctly no problem... but can someone please help me to rewrite this code so that ifstream.open would be used to read .txt file...
the problem states:
you can contain 10 kilograms in the knapsack, have three possible items, with weight/values of (6,700), (5,500), and (5, 400), the optimal answer would be to take the second and third items (index 1 and 2), getting a total value of 900
the .txt input should look like this:
10
3
6 700
5 500
5 400
here's my code:
Code:
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define MAXN 500 /* max items*/
#define MAXM 500 /* max capacity */
char set[MAXM][MAXN];
/* set[i][j]==1 means that for capacity i an optimal solution contains item j */
unsigned int Fn[MAXM]; /* objective function */
/* items */
/* No. 1 2 3 4 5 6 7 8 */
unsigned int m[MAXN] = {6, 5, 5}; /* volume */
unsigned int c[MAXN] = {700, 500, 400}; /* price */
unsigned int M = 70; /* actual capacity */
unsigned int N = 8; /* number of items */
void calculate()
{
unsigned int maxValue, maxIndex, i, j;
memset(set, 0, sizeof(set)); /* set[i][j] = 0 */
for (i=1; i<=M; i++)
{
maxValue = maxIndex = 0;
for (j=1; j<=N; j++) /* try the item j */
if (m[j]<=i && !set[i-m[j]][j])
if (c[j] + Fn[i-m[j]] > maxValue)
{
maxValue = c[j] + Fn[i-m[j]];
maxIndex = j;
}
if (maxIndex > 0) /* succesful ! */
{
Fn[i] = maxValue;
memcpy(set[i], set[i-m[maxIndex]], N);
set[i][maxIndex] = 1;
}
if (Fn[i] < Fn[i-1])
{
Fn[i] = Fn[i-1];
memcpy(set[i], set[i-1], N);
}
}
}
void write()
{
cout << Fn[M] << endl;
for (int i=1; i<=N; i++)
if (set[M][i])
cout << i << endl;
}
int main()
{
calculate();
write();
return 0;
}
i don't understand how to properly use the fstream so that it would correctly communicate with the functions and variable above
please help me to rewrite this program by adding ifstream in it
thank you
Last edited by eidalina20; October 8th, 2007 at 08:08 PM.
Reason: needed to put code into [code] tags
-
October 8th, 2007, 07:28 PM
#2
Re: please help with knapsack program
Put your code in code tags, see faq on how to do this. (pls edit your post so ppl have an easier job reading your code).
You dont really state what the problem is, do you expect someone to code up the desired function?
You already know that you can use ifstream to open a file. So do that. Or explain what exactly it is, you have problems with.
-
October 9th, 2007, 11:55 AM
#3
Re: please help with knapsack program
Originally Posted by eidalina20
i don't understand how to properly use the fstream so that it would correctly communicate with the functions and variable above
Why dont you try coding up the function? You can use this tutorial: http://www.cplusplus.com/doc/tutorial/files.html
The tactic i would use is: Read a line from the file into a string, make a stringstream of that string, then use that to convert the values in each line into your int values.
See here how to use a stringstream:
http://www.java2s.com/Tutorial/Cpp/0...ingstreams.htm
Btw: dont use unsigned ints to indicate the value cant be negative. You can still assign a negative value, and it will give undesired results.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|