# C++ Program to Solve the 0-1 Knapsack Problem

«
»
This is a C++ Program to solve 0-1 knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Here is source code of the C++ Program to Solve the 0-1 Knapsack Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include<stdio.h>`
2. `#include<conio.h>`
3. `#include<iostream>`
4. ` `
5. `using namespace std;`
6. ` `
7. `// A utility function that returns maximum of two integers`
8. `int max(int a, int b)`
9. `{`
10. `    return (a > b) ? a : b;`
11. `}`
12. ` `
13. `// Returns the maximum value that can be put in a knapsack of capacity W`
14. `int knapSack(int W, int wt[], int val[], int n)`
15. `{`
16. `    // Base Case`
17. `    if (n == 0 || W == 0)`
18. `        return 0;`
19. ` `
20. `    // If weight of the nth item is more than Knapsack capacity W, then`
21. `    // this item cannot be included in the optimal solution`
22. `    if (wt[n - 1] > W)`
23. `        return knapSack(W, wt, val, n - 1);`
24. ` `
25. `    // Return the maximum of two cases: (1) nth item included (2) not included`
26. `    else`
27. `        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),`
28. `                knapSack(W, wt, val, n - 1));`
29. `}`
30. ` `
31. `// Driver program to test above function`
32. `int main()`
33. `{`
34. `    cout << "Enter the number of items in a Knapsack:";`
35. `    int n, W;`
36. `    cin >> n;`
37. `    int val[n], wt[n];`
38. `    for (int i = 0; i < n; i++)`
39. `    {`
40. `        cout << "Enter value and weight for item " << i << ":";`
41. `        cin >> val[i];`
42. `        cin >> wt[i];`
43. `    }`
44. ` `
45. `    //    int val[] = { 60, 100, 120 };`
46. `    //    int wt[] = { 10, 20, 30 };`
47. `    //    int W = 50;`
48. `    cout << "Enter the capacity of knapsack";`
49. `    cin >> W;`
50. `    cout << knapSack(W, wt, val, n);`
51. ` `
52. `    return 0;`
53. `}`

Output:

```\$ g++ 0-1Knapsack.cpp
\$ a.out

Enter the number of items in a Knapsack:5
Enter value and weight for item 0:11 111
Enter value and weight for item 1:22 121
Enter value and weight for item 2:33 131
Enter value and weight for item 3:44 141
Enter value and weight for item 4:55 151
Enter the capacity of knapsack 300
99```

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube 