Write a C++ program called knapscak.cpp that solves the Knapsack problem. Your p

Question

Write a C++ program called knapscak.cpp that solves the Knapsack problem. Your program should read a weight and a value of each item from a user and determine the best subset. Your program should also display all intermediate results. In this program, you can assume that the number of items and knapsack capacity (W) are less than 21. The following presents a sample run.
Enter a number of items: 4
Enter knapsack capacity: 5
Enter weights and values of 4 items:
Item 1: 2 12
Item 2: 1 10
Item 3: 3 20
Item 4: 2 15

ij: 0 1 2 3 4 5
0 : 0 0 0 0 0 0
1 : 0 0 12 12 12 12
2 : 0 10 12 22 22 22
3 : 0 10 12 22 30 32
4 : 0 10 15 25 30 37

Final Vale: 37
Subset: item 1, item 2, item 4

Explanation / Answer

#include const int max=30; int MFKS(int,int); int maximum(int,int); int value[30]; int weight[30]; int v[30][30]; int x[30]; int N,M; int MFKS(int i,int j) { int val; if(v[i][j]==-1) { if(j=0;i--) { if(v[i][j1]!=v[i-1][j1]) { x[i]=1; j1=j1-weight[i]; } } for(int i=1;i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---