Write a C++ program called knapsack.cpp to solve the Knapsack problem. For detai
ID: 3809995 • Letter: W
Question
Write a C++ program called knapsack.cpp to solve the Knapsack problem. For details, read the textbook page 116 ~ 118. Your program should read the weight and value of each item from a user and determine the best subset. In the program, you can assume that the number of items is less than 15. And also, you should assume that each item have only one. To get the full credits, your program should display all combinations of the item(s). However, the sequence of sets displayed on the screen is not important.
This is a sample result of the C++ program.
Enter a number of items: 2
Enter knapsack capacity: 5
Enter weights and values of 2 items:
Item 1: 3 12
Item 2: 4 10
set 1: {} => capacity: 0, value: $0
set 2: {1} => capacity: 3, value: $12
set 3: {2} => capacity: 4, value: $10
set 4: {1,2} => capacity: 7 – over capacity, value: N/A
Solution: {1} => capacity: 3, value: $12
In the same run, the sequence of sets is not important. For example, if your program displays like below, this is fine as well.
Enter a number of items: 2
Enter knapsack capacity: 5
Enter weights and values of 2 items:
Item 1: 3 12
Item 2: 4 10
set 1: {} => capacity: 0, value: $0
set 2: {2} => capacity: 4, value: $10
set 3: {1} => capacity: 3, value: $12
set 4: {1,2} => capacity: 7 – over capacity, value: N/A
Solution: {1} => capacity: 3, value: $12
Explanation / Answer
#include <iostream>
using namespace std;
// A utility function that returns maximum of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w]
= max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main()
{
cout << "Enter the number of items in a Knapsack:";
int n, W;
cin >> n;
int val[n], wt[n];
for (int i = 0; i < n; i++)
{
cout << "Enter value and weight for item " << i << ":";
cin >> val[i];
cin >> wt[i];
}
// int val[] = { 60, 100, 120 };
// int wt[] = { 10, 20, 30 };
// int W = 50;
cout << "Enter the capacity of knapsack";
cin >> W;
cout << knapSack(W, wt, val, n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.