Question

Suppose you won a shopping spree and you can take any number of items from the Amazon store (assume that there is only one copy of each item). There are n items in the store each of value v[1..n] and weights w[1..n]. You are given a trolley that can only carry a total of W weight of items. Don't worry about the size of the items, they would somehow magically fit in the trolley. You want to find the maximum value of items that you can pick. Being a programmer you decide to use dynamic programming to solve this problem. Write the recurrence formula that would represent the approach of your solution. Mention both the base case and the recursive case of the recurrence formula.

Answer 1

The recurrence formula for solving the maximum value of items problem using dynamic programming can be defined in two cases: when the current item's weight is less than the total weight of the trolley, and when the current item's weight is greater than or equal to the total weight of the trolley. The base case is when the total weight of the trolley is 0 or all items have been considered.

Step-by-step explanation:

The recurrence formula for this problem can be defined as follows:

If the total weight of the trolley (W) is less than the weight of the current item (w[i]), then the maximum value that can be picked is the same as the maximum value that can be picked without considering the current item, i.e., f(i, W) = f(i-1, W).

If the total weight of the trolley (W) is greater than or equal to the weight of the current item (w[i]), then we have two options:

The base case for this recurrence formula is when either the total weight of the trolley (W) is 0 or we have considered all the items (i = 0).

In either case, the maximum value that can be picked is 0.