Knapsack 2

A simple solution is to generate weights for all possible values of items and take the one which has sum of values as maximum and total weight less than or equal to ‘W’.
 

The maximum total value of items will be simply sum of values of all items. We can loop through all these values and check for a particular value what weight these items have. This weight must be less than or equal to our knapsack capacity ‘W’. And we take a maximum of all these values.
 

Now, for finding the total weight for a particular value we can use recursion because we will generate all possible subsets of items. We are just finding what is the least weight Ninja need to carry to get a particular value.
 

For i-th item there will be two choices:

1. Get included in the subset - In this case, we include the current item in our final subset and recur for further indices and also the value for which we are finding weight will be reduced by the value of the current item. This case is only possible when the value of the current item is less than the value for which we are finding weight.
2. Don’t get included - In this case, we don’t include the current item and directly recur for further indices with the same weight.
    

Then we will just take the minimum of these two cases as we want to find the least weight Ninja need to carry.

The steps are as follows :

1. Declare a variable ‘maximumValue’, which will store the maximum value which we can obtain from given values.
2. for ‘i’ in [0, .. N - 1]:
   • ‘maximumValue’ += value[i]
3. Declare a variable ‘ans’ to store the maximum value Ninja can take home.
4. As we need to find a maximum value that has weights of items less than ‘W’, we can iterate from behind.
5. for ‘v’ in [maximumValue, .. 0]:
   • if knapsackHelper(0, v) <= ‘W’:
     • ‘ans’ = v
     • break
6. knapsackHelper(idx, val):
   • if ‘idx’ == ‘N’:
     • if ‘val’ == 0:
       • return 0
     • else
       • return infinity
   • Declare two variable ‘inc’ and ‘exc’ which will store weight including the current item and weight excluding current item respectively and initialize them to infinity.
   • if ‘val’ >= ‘VALUE[idx]’:
     • ‘inc’ = knapsackHelper(idx + 1, val - VALUE[idx]) + WEIGHT[idx].
   • ‘exc’ = knapsackHelper(idx + 1, val)
   • return min(inc, exc)

The solution which we discussed in the previous approach was exponential and will result in a time-out. If we loop closely there will be many overlapping subproblems in that problem. Hence if we store result calculated for a particular state we might use that later.
 

We can memoize the above solution. As there are two variables changing there will be two states in our DP table. 
 

DP[i][j] will denote the minimum weight using first ‘i’ items and value ‘j’.
 

The steps are as follows :

1. Declare a variable ‘maximumValue’, which will store the maximum value which we can obtain from given values.
2. Declare a variable ‘ans’ to store the maximum value Ninja can take home.
3. for ‘i’ in [0, .. N - 1]:
   • ‘maximumValue’ += value[i]
4. Declare a 2d array ‘DP’ of size ‘N’ X (‘maximumValue’ + 1) and initialize all values to -1.
5. As we need to find a maximum value that has weights of items less than ‘W’, we can iterate from behind.
6. for ‘v’ in [maximumValue, .. 0]:
   • if knapsackHelper(0, v) <= ‘W’:
     • ‘ans’ = v
     • break
7. knapsackHelper(idx, val):
   • if ‘idx’ == ‘N’:
     • if ‘val’ == 0:
       1. return 0
     • else
       1. return infinity
   • if ‘DP[idx][val]’ != -1:
     • return DP[idx][val]
   • Declare two variable ‘inc’ and ‘exc’ which will store weight including the current item and weight excluding current item respectively and initialize them to infinity.
   • if ‘val’ >= ‘VALUE[idx]’:
     • ‘inc’ = knapsackHelper(idx + 1, val - VALUE[idx]) + WEIGHT[idx].
   • ‘exc’ = knapsackHelper(idx + 1, val)
   • return DP[idx][val] = min(inc, exc)

In this approach, we will construct our DP table in a bottom-up manner. We will calculate all minimum weights for all values of items from 0 to the sum of all values of items.
 

DP[i][j] will contain minimum weight having value ‘j’ using first ‘i’ items.
 

Initially, it will be filled with infinity because it will help in comparing minimum weights.
 

Base condition will be DP[0][j] = 0 for all j in [0, .. maximumValue], because we can get 0 minimum weight by taking 0 items.
 

DP[i][j] can be calculated by either including ‘i’-th item or excluding ‘i’-th item. 
 

So, DP[i][j] will be initially equal to DP[i - 1][j] (Excluding)
 

if VALUE[i] <= j, which means we can include ‘i’-th item, then we will take minimum of (DP[i][j], DP[i - 1][j - VALUE[i]] + WEIGHT[i]).
 

After generating all minimum weights we will check for which values the weight is less than or equal to ‘W’. And all of these values we will take the maximum value.
 

The steps are as follows :

1. Declare a variable ‘maximumValue’, which will store the maximum value which we can obtain from given values.
2. Declare a variable ‘ans’ to store the maximum value Ninja can take home.
3. for ‘i’ in [0, .. N - 1]:
   • ‘maximumValue’ += value[i]
4. Declare a 2d array ‘DP’ of size (‘N’ + 1) X (‘maximumValue’ + 1) and initialize all values to infinity.
5. Fill the first column i.e. Base Condition.
6. for ‘i’ in [0, .. N]:
   • DP[i][0] = 0
7. for ‘i’ in [1, .. N]:
   • for ‘j’ in [1, .. maximumValue]:
     • DP[i][j] = DP[i - 1][j]
     • if VALUE[i - 1] <= ‘j’:
       • DP[i][j] = min(DP[i][j], DP[i - 1][j - VALUE[i - 1]] + WEIGHT[i - 1])
8. As we need to find a maximum value that has weights of items less than ‘W’, we can iterate from behind.
9. for ‘v’ in [maximumValue, .. 1]:
   • if DP[n][v] <= ‘W’:
     • ‘ans’ = v
     • break
10. Finally, return ‘ans’.