fork(2) download
copy 
  1. #include <stdio.h>
  2.  
  3. #define max(a,b) (a > b ? a : b)
  4.  
  5. int matrix[100][100] = {0};
  6. int picks[100][100] = {0};
  7. int subset[100];
  8. int knapsack(int nItems, int size, int weights[], int values[]){
  9.     int i,j;
  10.  
  11.     for (i=1;i<=nItems;i++){
  12.         for (j=0;j<=size;j++){
  13.             if (weights[i-1]<=j){
  14.                 matrix[i][j] = max(matrix[i-1][j],values[i-1]+matrix[i-1][j-weights[i-1]]);
  15.                 if (values[i-1]+matrix[i-1][j-weights[i-1]]>matrix[i-1][j])
  16.                     picks[i][j]=1;
  17.                 else
  18.                     picks[i][j]=-1;
  19.             }
  20.             else{
  21.                 picks[i][j] = -1;
  22.                 matrix[i][j] = matrix[i-1][j];
  23.             }
  24.         }
  25.     }
  26.  
  27.     return matrix[nItems][size];
  28.  
  29. }
  30.  
  31. void printPicks(int item, int size, int weights[]){
  32. 	int k=0;
  33.     while (item>0){
  34.         if (picks[item][size]==1){
  35.             subset[k++]=item;
  36.             item--;
  37.             size -= weights[item];
  38.         }
  39.         else{
  40.             item--;
  41.         }
  42.     }
  43.     //Your subset here
  44.     for(int i=k-1;i>=0;--i)
  45. 		printf("%d ",subset[i]);
  46.  
  47.  
  48. return;
  49. }
  50.  
  51. int main(){
  52.  
  53. int nItems = 3;
  54.     int knapsackSize = 11;
  55.     int weights[] = {4,10,5};
  56.     int values[] = {15,12,8};
  57.  
  58.     printf("Max value = %d\n",knapsack(nItems,knapsackSize,weights,values));
  59.  
  60.     printf("Subset are: ");
  61.  
  62.     printPicks(nItems,knapsackSize, weights);
  63.  
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0s 16136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max value = 23
Subset are: 1 3
https://ideone.com/qpOqBv
language:
C++14 (gcc 8.3)
created:
7 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!