CODEWITHSUNDEEP
recursiondynamic-programmingknapsack-problem
Chaitanya Baranwal
Chaitanya Baranwal

Reputation: 42

Knapsack variation

So I have an array of coupons, each with a price and the quantity of items that can be bought from it. I can only buy the given item quantity from a coupon, no more, no less. How to find the minimum cost to get the required number of items with coupons (and return -1 if not possible)?

For example, on having 4 coupons: "Buy 3 at 10 dollars", "Buy 2 at 4 dollars", "Buy 2 at 4 dollars" and "Buy 1 at 3 dollars", and 4 items to buy, the minimum cost is 8 dollars.

Knapsack works on finding maximums, but for minimum it'll just keep on not considering any coupon and come up with an answer of 0.

Here's my code:

int minimumCost(coupon_t coupons[], int numCoupons, int units) {

    if (units <= 0 || numCoupons <= 0)
        return 0;

    if (coupons[numCoupons-1].quantity > units)
        return minimumCost(coupons, numCoupons-1, units);

    coupon_t coupon = coupons[numCoupons-1];
    return min(coupon.price + minimumCost(coupons, numCoupons-1, units-coupon.quantity),
            minimumCost(coupons, numCoupons-1, units));

}

Upvotes: 0

Views: 324

Answers (1)

Amadan
Amadan

Reputation: 198324

Had a little more think about this. The key, as you say, is handling of 0. In typical knapsack code, 0 has two meanings: both "not buying" and "can't buy". Splitting those seems to work:

def minimum_cost(coupons, units, coupon_no=0):
    if units < 0 or coupon_no == len(coupons):
        # special value for "impossible"
        return None

    if units == 0:
        # no more space, so we're not buying anything else
        return 0

    quantity, price = coupons[coupon_no]
    next_coupon = coupon_no + 1

    if quantity > units:
        return minimum_cost(coupons, units, next_coupon)

    pre_purchase_value_when_used = minimum_cost(coupons, units - quantity, next_coupon)
    value_when_unused = minimum_cost(coupons, units, next_coupon)

    # return whichever is not impossible, or cheaper of two possibilities:
    if pre_purchase_value_when_used is None:
        return value_when_unused
    elif value_when_unused is None:
        return pre_purchase_value_when_used + price
    else:
        return min(pre_purchase_value_when_used + price, value_when_unused)

coupons = [[3, 10], [2, 4], [2, 4], [1, 3]]
units = 4
cost = minimum_cost(coupons, units)
print(cost)
# => 8

(Note that is not , unless you cache the function results, although it shouldn't be too hard to make it use a table. The key insight about dynamic programming is to use storage to avoid recalculating things we already calculated.)

Upvotes: 1

Related Questions