fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int knapsack (int W, int wt[], int val[], int n) {
  5.   int K[n+1][W+1] = {0};
  6.  
  7.   // Building table K[][] in bottom manner
  8.   for(int i=0; i<=n; i++) {
  9.     for(int w=0; w <= W; w++) {
  10.       // Base case: empty knapsack
  11.       if (i == 0 || w == 0) {
  12.         K[i][w] = 0;
  13.       } else if (wt[i-1] <= w) {
  14.         // Selecting val[i-1] if it gives higher
  15.         // knapsack value
  16.         K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
  17.                    K[i-1][w]);
  18.       } else {
  19.         // Not including val[i-1]: 
  20.         // if wt[i-1] is greater than 
  21.         // available knapsack capacity
  22.         K[i][w] = K[i-1][w];
  23.       }
  24.     }
  25.   }
  26.   return K[n][W];
  27. }
  28.  
  29.  
  30. int main() {
  31. 	// your code goes here
  32.   int val[] = {60, 100, 120};
  33.   int wt[] = {10, 20, 30};
  34.   int W = 50, n = 3;
  35.   printf("%d", knapsack(W, wt, val, n));
  36.   return 0;
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 5644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
220
https://ideone.com/int4ud
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

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!