寻找最适合于特定数量的元素的算法

Question

我正在寻找一个算法来解决下面的问题(我会用一个例子来解释它)：

假设我有10.000美元的可用金额和以下成本，我可以用我的金额融资：

成本1: 1.000美元

成本2: 3.000美元

成本3: 4.000美元

成本4: 5.000美元

成本不能部分支付，所以你要么支付全部成本，要么根本不支付。我正在寻找的是一种算法，它可以帮助我找到不会超过可用金额的成本组合，但另一方面使用大部分或全部可用金额。

在我的例子中是:成本1+成本3+成本4。

我还想添加一个参数，该参数确定可以最大限度地资助多少成本。如果我在我的示例中说只能支付两个成本，那么将返回cost 3和cost 4。

我的方法是检查所有可用的组合，对它们进行求和，然后选择最充分利用可用数量的组合。然而，我想知道是否有最简单的方法来找到最佳组合。

Answer 1

这是一个简单的动态编程问题(背包的变体)。状态可以定义为positionhow_many_bills_can_be_paid。下面是一个递归解决方案：

假设C是开销数组，memo初始化为-1：

const int N = 10;    //number of notes to pay
int memo[N][M][K];   //remember to initialize it with -1

int func(int cur_index,int rest_amount,int K){

    if(cur_index == N){
        return 0;
    }

    int &ret = memo[cur_index][rest_amount][K];
    if(ret != -1) return ret;    //memoization ensures we won't solve the same sub problem more than once
    ret = 0;
    if(rest_amount >= C[cur_index]  && K > 0 )
    ret = func(cur_index+1,cost+C[cur_index],K-1);

    ret = max(ret,func(cur_index+1,cost,K);

    return ret;
}

Answer 2

你可以对列表进行排序，并选择最上面的，直到你的预算耗尽。它也可用于装箱，并保证在一定范围内达到最优。

Answer 3

我不能改进你的通用数据解决方案，但是有一些改进可以提高它的速度。

如果N总量非常低，有一个简单的动态解决方案：

setOfValues
put totalAmount to setOfValues
foreach cost do
    foreach amount in setOfValues do
        if (amount - cost) > 0 and not exists (amount - cost) in setOfValues
            put (amount - cost) to setOfValues
get lowest setOfValues

您可以简单地将其升级到其他要求(例如最高x成本)。