fork download
copy 
  1. // A dynamic programming based
  2. // solution for 0-1 Knapsack problem
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // A utility function that returns
  7. // 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
  14. // can be put in a knapsack of capacity W
  15. int knapSack(int W, int wt[], int val[], int n)
  16. {
  17.     int i, w;
  18.     int K[n + 1][W + 1];
  19.  
  20.     // Build table K[][] in bottom up manner
  21.     for(i = 0; i <= n; i++)
  22.     {
  23.         for(w = 0; w <= W; w++)
  24.         {
  25.             if (i == 0 || w == 0)
  26.                 K[i][w] = 0;
  27.             else if (wt[i - 1] <= w)
  28.                 K[i][w] = max(val[i - 1] +
  29.                                 K[i - 1][w - wt[i - 1]],
  30.                                 K[i - 1][w]);
  31.             else
  32.                 K[i][w] = K[i - 1][w];
  33.         }
  34.     }
  35.     return K[n][W];
  36. }
  37.  
  38. // // Driver Code
  39. // int main()
  40. // {
  41. //     int val[] = { 60, 100, 120 };
  42. //     int wt[] = { 10, 20, 30 };
  43. //     int W = 50;
  44. //     int n = sizeof(val) / sizeof(val[0]);
  45.  
  46. //     cout << knapSack(W, wt, val, n);
  47.  
  48. //     return 0;
  49. // }
  50.  
  51. // Driver Code
  52. int main()
  53. {
  54.     int val[] = {100,100,100,100,100};
  55.     int wt[] = {1,2,1,2,1};
  56.     int W = 10;
  57.     int n = sizeof(val) / sizeof(val[0]);
  58.     cout << knapSack(W, wt, val, n);
  59.     return 0;
  60. }
Success #stdin #stdout 0s 5608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500
https://ideone.com/VQ1ICb
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!