fork(1) download
copy 
  1. #include <stdio.h>
  2. #define min(a,b) (a < b ? a : b)
  3. #define INF 10000000
  4.  
  5. int matrix[100][100] = {0};
  6.  
  7. int knapsack(int index, int size, int weights[],int values[]){
  8.     int take = INF;
  9.  
  10.     if (index == -1){
  11.         if(size == 0) return 0;
  12.         else return INF;
  13.     }
  14.  
  15.     if (matrix[index][size]!=-1)
  16.         return matrix[index][size];
  17.  
  18.     for(int itemcount = 0;(itemcount * weights[index]) <= size;itemcount++){
  19.         if ((weights[index] * itemcount) <= size) 
  20.             take = min(take, (values[index] * itemcount) + knapsack(index - 1, size - (itemcount * weights[index]), weights, values)); //knapsack(index) and not //knapsack(index-1) 
  21.     }
  22.  
  23.     matrix[index][size] = take;
  24.  
  25.     return matrix[index][size];
  26.  
  27. }
  28.  
  29. int main(){
  30.     int nItems = 4;
  31.     int knapsackSize = 10;
  32.     int weights[4] = {5,4,6,3};
  33.     int values[4] = {1,1,1,1};
  34.     for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) matrix[i][j] = -1;
  35.  
  36.     printf("Min value = %d\n",knapsack(nItems-1,knapsackSize,weights,values));
  37.  
  38.     return 0;
  39. }
Success #stdin #stdout 0s 3496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Min value = 2
https://ideone.com/TNycZo
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!