C++ Program to Solve Knapsack Problem Using Dynamic Programming

«
»
This is a C++ Program to knapsack problem using dynamic programming. 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 Knapsack Problem Using Dynamic Programming. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `// A Dynamic Programming based solution for 0-1 Knapsack problem`
2. `#include <iostream>`
3. ` `
4. `using namespace std;`
5. ` `
6. `// A utility function that returns maximum of two integers`
7. `int max(int a, int b)`
8. `{`
9. `    return (a > b) ? a : b;`
10. `}`
11. ` `
12. `// Returns the maximum value that can be put in a knapsack of capacity W`
13. `int knapSack(int W, int wt[], int val[], int n)`
14. `{`
15. `    int i, w;`
16. `    int K[n + 1][W + 1];`
17. ` `
18. `    // Build table K[][] in bottom up manner`
19. `    for (i = 0; i <= n; i++)`
20. `    {`
21. `        for (w = 0; w <= W; w++)`
22. `        {`
23. `            if (i == 0 || w == 0)`
24. `                K[i][w] = 0;`
25. `            else if (wt[i - 1] <= w)`
26. `                K[i][w]`
27. `                        = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);`
28. `            else`
29. `                K[i][w] = K[i - 1][w];`
30. `        }`
31. `    }`
32. ` `
33. `    return K[n][W];`
34. `}`
35. ` `
36. `int main()`
37. `{`
38. `    cout << "Enter the number of items in a Knapsack:";`
39. `    int n, W;`
40. `    cin >> n;`
41. `    int val[n], wt[n];`
42. `    for (int i = 0; i < n; i++)`
43. `    {`
44. `        cout << "Enter value and weight for item " << i << ":";`
45. `        cin >> val[i];`
46. `        cin >> wt[i];`
47. `    }`
48. ` `
49. `    //    int val[] = { 60, 100, 120 };`
50. `    //    int wt[] = { 10, 20, 30 };`
51. `    //    int W = 50;`
52. `    cout << "Enter the capacity of knapsack";`
53. `    cin >> W;`
54. `    cout << knapSack(W, wt, val, n);`
55. ` `
56. `    return 0;`
57. `}`

Output:

```\$ g++ DPKnapsack.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.