C++ Program to Solve the 0-1 Knapsack Problem

«
»
This is a C++ Program to solve 0-1 knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Here is source code of the C++ Program to Solve the 0-1 Knapsack Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<conio.h>
  3. #include<iostream>
  4.  
  5. using namespace std;
  6.  
  7. // A utility function that returns maximum of two integers
  8. int max(int a, int b)
  9. {
  10.     return (a > b) ? a : b;
  11. }
  12.  
  13. // Returns the maximum value that can be put in a knapsack of capacity W
  14. int knapSack(int W, int wt[], int val[], int n)
  15. {
  16.     // Base Case
  17.     if (n == 0 || W == 0)
  18.         return 0;
  19.  
  20.     // If weight of the nth item is more than Knapsack capacity W, then
  21.     // this item cannot be included in the optimal solution
  22.     if (wt[n - 1] > W)
  23.         return knapSack(W, wt, val, n - 1);
  24.  
  25.     // Return the maximum of two cases: (1) nth item included (2) not included
  26.     else
  27.         return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
  28.                 knapSack(W, wt, val, n - 1));
  29. }
  30.  
  31. // Driver program to test above function
  32. int main()
  33. {
  34.     cout << "Enter the number of items in a Knapsack:";
  35.     int n, W;
  36.     cin >> n;
  37.     int val[n], wt[n];
  38.     for (int i = 0; i < n; i++)
  39.     {
  40.         cout << "Enter value and weight for item " << i << ":";
  41.         cin >> val[i];
  42.         cin >> wt[i];
  43.     }
  44.  
  45.     //    int val[] = { 60, 100, 120 };
  46.     //    int wt[] = { 10, 20, 30 };
  47.     //    int W = 50;
  48.     cout << "Enter the capacity of knapsack";
  49.     cin >> W;
  50.     cout << knapSack(W, wt, val, n);
  51.  
  52.     return 0;
  53. }

Output:

advertisement
$ g++ 0-1Knapsack.cpp
$ a.out
 
Enter the number of items in a Knapsack:5
Enter value and weight for item 0:11 111
Enter value and weight for item 1:22 121
Enter value and weight for item 2:33 131
Enter value and weight for item 3:44 141
Enter value and weight for item 4:55 151
Enter the capacity of knapsack 300
99

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter