{"id":895,"date":"2025-08-13T19:44:59","date_gmt":"2025-08-13T14:14:59","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=895"},"modified":"2025-08-13T19:45:00","modified_gmt":"2025-08-13T14:15:00","slug":"0-1-knapsack-problem","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/0-1-knapsack-problem\/","title":{"rendered":"0 – 1 Knapsack Problem | 5 DP Solutions in Python"},"content":{"rendered":"\n

Given n<\/strong> items, each with a specific weight<\/strong> and value<\/strong>, and a knapsack with a capacity of W<\/strong>, the task is to put the items in the knapsack such that the sum of weights of the items <= W<\/strong> and the sum of values <\/strong>associated with them is maximized<\/strong>. <\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Note: <\/strong>You can either place an item entirely in the bag or leave it out entirely. Also, each item is available in single <\/strong>quantity.<\/p>\n\n\n\n

Examples :<\/strong><\/p>\n\n\n\n

Input: <\/strong>W = 4, val[]<\/code> = [1, 2, 3], wt[]<\/code> = [4, 5, 1] 
Output: <\/strong>3
Explanation: <\/strong>Choose the last item, which weighs 1 unit and has a value of 3.<\/pre>\n\n\n\n
Input:<\/strong> W = 3, val[]<\/code> = [1, 2, 3], wt[]<\/code> = [4, 5, 6] 
Output: <\/strong>0
Explanation: <\/strong>Every item has a weight exceeding the knapsack's capacity (3).<\/pre>\n\n\n\n
Input:<\/strong> W = 5, val[]<\/code> = [10, 40, 30, 50], wt[]<\/code> = [5, 4, 2, 3] 
Output: <\/strong>80
Explanation: <\/strong>Choose the third item (value 30, weight 2) and the last item (value 50, weight 3) for a total value of 80.<\/pre>\n\n\n\n
Constraints:<\/strong>
2 \u2264 val.size() = wt.size() \u2264 103<\/sup>
1 \u2264 W \u2264 103<\/sup>
1 \u2264 val[i] \u2264 103<\/sup>
1 \u2264 wt[i] \u2264 103<\/sup><\/p>\n\n\n
\n\t\t\t
\n\t\t\t\t
Contents:<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
\n\t\t\t
\n\t\t\t\t