## 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 *c*_{i} 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 *s*_{i} associated with it and we can select an item *s*_{i} times (1 ≤ *i* ≤ *N*).

## Solving bounded knapsack problem

The solution is simple. Let *dp*[*i*][*j*] be the minimum count of *i*th 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 *i*th 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).

Auto comment: topic has been updated by sdnr1 (previous revision, new revision, compare).Another tutorial about it.

Can you provide links for some sample problems where this technique is needed?

Original approach: http://codeforces.com/blog/entry/49793 (755F)

Alternative approach: http://codeforces.com/blog/entry/49793?#comment-337708

Auto comment: topic has been updated by sdnr1 (previous revision, new revision, compare).another problem related to Optimizing 0/1 Knapsack http://codeforces.com/contest/95/problem/E?mobile=false