动态编程:最大化要买的东西的数量

Question

例如，对于一个产品，我们有一个列表，其中列出了您购买的产品数量以及您使用该数量的产品支付的相应价格：

数字= {1，5，8，12}

价格= { 0.5，2，3，3.6} (即1个产品支付0.5，5个产品支付2，以此类推)

现在我需要使用固定数量的美元来购买尽可能多的产品。我如何使用动态编程来实现这一点？

如果我想购买固定数量的产品，我知道如何将成本降到最低。但是对于固定的金额，我感到困惑，因为价格是双精度类型的，我不能用价格索引an数组来做到这一点。

Answer 1

对产品数量执行二进制搜索，然后使用固定数量的产品最小化成本。

我想这也可以用贪婪来解决。将pricePerProduct = pricei / numberi，pricei，numberi存储在一个数组中，并对该数组进行排序。遍历数组。对于第i个指数，您可以购买floor( remainingDollar /)* number of products。价格将更新为floor( remainingDollar / remainingDollar )* pricei