### sdnr1's blog

By sdnr1, history, 3 years ago,

## Problem Statement

We are going to deal with the well known knapsack problem with an additional constraint. We are given a list of N items and a knapsack of size W. Every item has a cost ci associated with it (1 ≤ i ≤ N). We can select some items from the list such sum of the cost of all the selected items does not exceed W. The goal is tell for all w (0 ≤ w ≤ W), if we can select any number of items such that their total cost equals w. This is also known as the 0/1 knapsack problem. This can be easily solved in O(NW) time complexity using standard knapsack approach.

The addition constraint we have is .

## The bounded knapsack problem

The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count si associated with it and we can select an item si times (1 ≤ i ≤ N).

## Solving bounded knapsack problem

The solution is simple. Let dp[i][j] be the minimum count of ith item that has to be used to get a total cost of j while using some number (possibly 0) of first i items. If a total cost of j can not be obtained using first i items, then dp[i][j] =  - 1. The following code is used to calculate dp[i][j],

if(dp[i-1][j] >= 0)
dp[i][j] = 0;
else if(dp[i][j - c[i]] >= 0 and dp[i][j - c[i]] < s[i])
dp[i][j] = dp[i][j - c[i]] + 1;
else
dp[i][j] = -1;


Here, c[i] is the cost and s[i] is the count for ith item. Also, dp[0][j] =  - 1 for all 1 ≤ j ≤ W and dp[0][0] = 0. Time complexity is O(NW).

## Optimizing 0/1 Knapsack

Now we can present a faster solution to our problem. Notice that number of items is N and . Hence, there can only be unique costs. So we convert our problem to a bounded knapsack problem with unique items having some count. This can be solved in !!!

PS: I wrote this blog since I could not find a good source on the internet to learn about this approach. I hope there is no error since I really didn't read about this anywhere and worked out this approach myself.

EDIT: As some people have pointed out, this method has been discussed in some previous blogs (see comments for links). The only practise problem I could find is 755F. Also, the method discussed in this blog is not the most optimal one possible and can be optimized further using a bitset (which I will discuss in a future blog).

• +119

 » 3 years ago, # |   0 Auto comment: topic has been updated by sdnr1 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Another tutorial about it.
 » 3 years ago, # | ← Rev. 2 →   0 Can you provide links for some sample problems where this technique is needed?
 » 3 years ago, # |   0 Original approach: http://codeforces.com/blog/entry/49793 (755F)Alternative approach: http://codeforces.com/blog/entry/49793?#comment-337708
 » 3 years ago, # |   0 Auto comment: topic has been updated by sdnr1 (previous revision, new revision, compare).
 » 3 years ago, # |   +8 another problem related to Optimizing 0/1 Knapsack http://codeforces.com/contest/95/problem/E?mobile=false
 » 6 weeks ago, # |   -66 hey, we r eagerly waiting for ur future blog ...
 » 6 weeks ago, # |   -65 oo sry didnt know that ur friends and supporters were so sensitive , will take care of commenting on blogs from now..
 » 6 weeks ago, # |   -42 wow
•  » » 4 weeks ago, # ^ |   -13 Why your above three comments received so much negative feedback?
•  » » » 4 weeks ago, # ^ |   -8 Because, a beginner like me didn't knew that commenting on an old blog will bring that to recent actions, now most probably our's comments will be downvoted too..Congrats!!
 » 6 weeks ago, # |   -16 Wooww