Users Online

· Guests Online: 107

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads
No Threads created
Hottest Threads
No Threads created

Latest Articles

C++ Program to Solve Knapsack Problem Using Dynamic Programming

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

 

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.

No Ratings have been Posted.
Render time: 0.65 seconds
10,266,820 unique visits