C++ Program to Solve Knapsack Problem Using Dynamic Programming

This is a C++ Program to knapsack problem using dynamic programming. 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 Knapsack Problem Using Dynamic Programming. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // A Dynamic Programming based solution for 0-1 Knapsack problem
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. // A utility function that returns maximum of two integers
  7. int max(int a, int b)
  8. {
  9.     return (a > b) ? a : b;
  10. }
  11.  
  12. // Returns the maximum value that can be put in a knapsack of capacity W
  13. int knapSack(int W, int wt[], int val[], int n)
  14. {
  15.     int i, w;
  16.     int K[n + 1][W + 1];
  17.  
  18.     // Build table K[][] in bottom up manner
  19.     for (i = 0; i <= n; i++)
  20.     {
  21.         for (w = 0; w <= W; w++)
  22.         {
  23.             if (i == 0 || w == 0)
  24.                 K[i][w] = 0;
  25.             else if (wt[i - 1] <= w)
  26.                 K[i][w]
  27.                         = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
  28.             else
  29.                 K[i][w] = K[i - 1][w];
  30.         }
  31.     }
  32.  
  33.     return K[n][W];
  34. }
  35.  
  36. int main()
  37. {
  38.     cout << "Enter the number of items in a Knapsack:";
  39.     int n, W;
  40.     cin >> n;
  41.     int val[n], wt[n];
  42.     for (int i = 0; i < n; i++)
  43.     {
  44.         cout << "Enter value and weight for item " << i << ":";
  45.         cin >> val[i];
  46.         cin >> wt[i];
  47.     }
  48.  
  49.     //    int val[] = { 60, 100, 120 };
  50.     //    int wt[] = { 10, 20, 30 };
  51.     //    int W = 50;
  52.     cout << "Enter the capacity of knapsack";
  53.     cin >> W;
  54.     cout << knapSack(W, wt, val, n);
  55.  
  56.     return 0;
  57. }

Output:

$ g++ DPKnapsack.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 Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.