fork download
copy 
  1. #include <stdio.h>
  2. #define max(a,b) (a > b ? a : b)
  3.  
  4. int matrix[100][100] = {0};
  5.  
  6. int knapsack(int index, int size, int weights[],int values[]){
  7.     int take,dontTake;
  8.  
  9.     take = dontTake = 0;
  10.  
  11.     if (matrix[index][size]!=0)
  12.         return matrix[index][size];
  13.  
  14.     if (index==0){
  15.         if (weights[0]<=size){
  16.             matrix[index][size] = values[0];
  17.             return values[0];
  18.         }
  19.         else{
  20.             matrix[index][size] = 0;
  21.             return 0;
  22.         }
  23.     }
  24.  
  25.     if (weights[index]<=size)
  26.         take = values[index] + knapsack(index-1, size-weights[index], weights, values);
  27.  
  28.     dontTake = knapsack(index-1, size, weights, values);
  29.  
  30.     matrix[index][size] = max (take, dontTake);
  31.  
  32.     return matrix[index][size];
  33.  
  34. }
  35.  
  36. int main(){
  37.     int nItems = 4;
  38.     int knapsackSize = 10;
  39.     int weights[4] = {5,4,6,3};
  40.     int values[4] = {1,1,1,1};
  41.  
  42.     printf("Max value = %dn",knapsack(nItems-1,knapsackSize,weights,values));
  43.  
  44.     return 0;
  45. }
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max value = 2n
https://ideone.com/POCSKT
language:
C++14 (clang 8.0)
created:
9 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!