背包变化

Question

所以我有一组优惠券，每张优惠券都有价格和可以从中购买的商品数量。我只能从优惠券中购买给定的商品数量，不能多也不能少。如何找到使用优惠券获得所需数量商品的最低成本（如果不可能，则 return -1）？

例如，拥有4张优惠券："Buy 3 at 10 dollars"、"Buy 2 at 4 dollars"、"Buy 2 at 4 dollars"和"Buy 1 at 3 dollars"，并购买4件商品，最低消费为8美元。

Knapsack 致力于寻找最大值，但对于最小值，它只会继续不考虑任何优惠券并得出答案 0。

这是我的代码：

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));

}

Answer 1

再考虑一下。正如您所说，关键是处理 0。在典型的背包代码中，0 有两个含义："not buying" 和 "can't buy"。拆分这些似乎可行：

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

（请注意 recursion is not dynamic-programming，除非您缓存函数结果，尽管使用 table 应该不会太难。关于动态规划的关键见解是使用存储以避免重新计算我们已经计算过的东西。）

背包变化

Knapsack variation

recursion

knapsack-problem

dynamic-programming