0/1 Knapsack Problem

 

Given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible. 

Note: The constraint here is we can either put an item completely into the bag or cannot put it at all [It is not possible to put a part of an item into the bag].

Examples:

Input: N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select the item with weight 4, the possible profit is 1. And if we select the item with weight 1, the possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the items with weight 4 and 1 together as the capacity of the bag is 4.

Input: N = 3, W = 3, profit[] = {1, 2, 3}, weight[] = {4, 5, 6}
Output: 0

Recursion Approach for 0/1 Knapsack Problem:

To solve the problem follow the below idea:

A simple solution is to consider all subsets of items and calculate the total weight and profit of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the subset with maximum profit.

Optimal Substructure: To consider all subsets of items, there can be two cases for every item. 

  • Case 1: The item is included in the optimal subset.
  • Case 2: The item is not included in the optimal set.

 To solve the problem follow the below idea:

Since subproblems are evaluated again, this problem has Overlapping Sub-problems property. So the 0/1 Knapsack problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computation of the same subproblems can be avoided by constructing a temporary array K[][] in a bottom-up manner. 

Illustration:

Below is the illustration of the above approach:

Let, weight[] = {1, 2, 3}, profit[] = {10, 15, 40}, Capacity = 6

  • If no element is filled, then the possible profit is 0.
weight⇢
item⇣/		0123456
00000000
1       
2       
3       
  • For filling the first item in the bag: If we follow the above mentioned procedure, the table will look like the following.
weight⇢
item⇣/		0123456
00000000
10101010101010
2       
3       
  • For filling the second item:  
    When jthWeight = 2, then maximum possible profit is max (10, DP[1][2-2] + 15) = max(10, 15) = 15.
    When jthWeight = 3, then maximum possible profit is  max(2 not put, 2 is put into bag) = max(DP[1][3], 15+DP[1][3-2]) = max(10, 25) = 25.
weight⇢
item⇣/		0123456
00000000
10101010101010
20101525252525
3       
  • For filling the third item:
    When jthWeight = 3, the maximum possible profit is max(DP[2][3], 40+DP[2][3-3]) = max(25, 40) = 40.
    When jthWeight = 4, the maximum possible profit is max(DP[2][4], 40+DP[2][4-3]) = max(25, 50) = 50.
    When jthWeight = 5, the maximum possible profit is max(DP[2][5], 40+DP[2][5-3]) = max(25, 55) = 55.
    When jthWeight = 6, the maximum possible profit is max(DP[2][6], 40+DP[2][6-3]) = max(25, 65) = 65.
weight⇢
item⇣/		0123456
00000000
10101010101010
20101525252525
30101540505565

Recursion without memorization approach:

Recursion with memorization approach:

2d DP approach

1d DP approach

 

 

 

Comments

Post a Comment

Popular posts from this blog

30. Substring with Concatenation of All Words

Problem Statement You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order. Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is "barfoo". It is the concaten...
Read more

Lowest common ancestor in a binary Tree

Approach Define a recursive function rec that takes three parameters: root (the current node), p (first node to find the lowest common ancestor for), and q (second node to find the lowest common ancestor for). Check if the current node root is null or if it is either p or q . If any of these conditions is true, return the current node root as the lowest common ancestor. Recursively call the rec function for the left subtree of the current node and assign the result to a variable l . Recursively call the rec function for the right subtree of the current node and assign the result to a variable r . Check if both l and r are not null. If so, it means that p and q are found on different subtrees of the current node, and the current node root is their lowest common ancestor. Return the current node root . If l is null, it means that both p and q are on the right subtree (or not present in the tree). Return r . If none of the above conditions are met, it means ...
Read more

New start day 1 : 30/09/2020 (codeforces 71A) Way to long strings

 Question:  source (codeforces: https://codeforces.com/problemset/problem/71/A) Way too long strings   Sometimes some words like " localization " or " internationalization " are so long that writing them many times in one text is quite tiresome. Let's consider a word  too long if its length is  strictly more  than  10  characters. All too long words should be replaced with a special abbreviation. This abbreviation is made like this: we write down the first and the last letter of a word and between them, we write the number of letters between the first and the last letters. That number is in the decimal system and doesn't contain any leading zeroes. Thus, " localization " will be spelled as " l10n ", and " internationalization » will be spelled as " i18n ". You are suggested to automatize the process of changing the words with abbreviations. At that, all too long words should be replaced by the abbreviation and the words th...
Read more