fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. const int W = 3;
  5. const int N = 3;
  6.  
  7. void printKnapsackTable (int K[][W+1]) {
  8. 	printf("\nKnapsack Table\n");
  9. 	for (int i=0; i<=N; i++) {
  10. 		for (int j=0; j<=W; j++) {
  11. 			printf("%d ", K[i][j]);
  12. 		}
  13. 		printf("\n");
  14. 	}
  15. }
  16.  
  17. void findKnapsackItems(int K[][W+1], int wt[], int val[]) {
  18. 	int i=N, res=K[N][W], w=W;
  19. 	printf("\nKnapsack Items:\n");
  20. 	while (i>0 && res>0) {
  21. 		if (res != K[i-1][w]) {
  22. 			printf("%d - %d is selected\n", i, val[i-1]);
  23. 			res = res - val[i-1];
  24. 			w = w - wt[i-1];
  25. 		}
  26. 		i=i-1;
  27. 	}
  28. }
  29.  
  30. int knapsack (int wt[], int val[], int K[][W+1]) {
  31.  
  32.   // Building table K[][] in bottom manner
  33.   for(int i=0; i<=N; i++) {
  34.     for(int w=0; w <= W; w++) {
  35.       // Base case: empty knapsack
  36.       if (i == 0 || w == 0) {
  37.         K[i][w] = 0;
  38.       } else if (wt[i-1] <= w) {
  39.         // Selecting val[i-1] if it gives higher
  40.         // knapsack value
  41.         K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
  42.                    K[i-1][w]);
  43.       } else {
  44.         // Not including val[i-1]: 
  45.         // if wt[i-1] is greater than 
  46.         // available knapsack capacity
  47.         K[i][w] = K[i-1][w];
  48.       }
  49.     }
  50.   }
  51.   return K[N][W];
  52. }
  53.  
  54.  
  55. int main() {
  56. 	// your code goes here
  57.   int val[] = {60, 100, 120};
  58.   int wt[] = {1, 2, 1};
  59.   int K[N+1][W+1] = {0};
  60.   printf("Knapsack Value: %d", knapsack(wt, val, K));
  61.   printKnapsackTable(K);
  62.   findKnapsackItems(K, wt, val);
  63.   return 0;
  64. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Knapsack Value: 220
Knapsack Table
0 0 0 0 
0 60 60 60 
0 60 100 160 
0 120 180 220 

Knapsack Items:
3 - 120 is selected
2 - 100 is selected
https://ideone.com/4pr1Zh
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 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!