0

我正在寻找一种算法来解决以下问题（我会用一个例子来解释）：

假设我有 10.000 美元的可用金额，并且可以使用我的金额支付以下费用：

成本 1: 1.000 $

成本 2: 3.000 $

成本 3: 4.000 $

成本 4: 5.000 $

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

在我的示例中，它将是：成本 1 + 成本 3 + 成本 4。

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

我的方法是检查所有可用的组合，将它们相加并选择最能使用可用数量的组合。但是，我想知道是否有最简单的方法可以找到最佳组合。

4

5 回答 5

1

这是一个简单的动态规划问题（背包的变体）。状态可以定义为 [position][rest_amount][how_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;
}
于 2013-07-29T14:35:31.550 回答
0

对于一般数据，我无法改进您的解决方案，但是很少有改进可以加快速度。

如果总量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成本）。

于 2013-07-29T12:34:34.763 回答
0

你的问题是一个NP问题；这个问题没有已知的解决方案可以保证在可接受的时间范围内找到最佳解决方案。真正找到最佳解决方案的唯一方法是尝试所有可能的解决方案，然后检查哪个是最佳解决方案。但是，如果您有成千上万的成本，那么这当然会非常缓慢。

所有其他比上述简单方法更快的解决方案都不能保证找到最佳解决方案。他们可能会找到一个好的解决方案，但您永远无法确定是否有更好的解决方案。

这与以下问题相同：您有一辆可以运输 X 磅货物的卡车，并且您有不同重量的货物。您的目标是充分利用可用容量。这个问题也被称为“背包问题”。除了本页列出的解决方案之外，没有其他已知的更好的解决方案。但是，它们都不能保证最佳结果。

于 2013-07-29T13:03:10.770 回答
0

您可以对列表进行排序并选择顶部，直到您的预算用尽。它也用于装箱，并保证在最佳范围内。

于 2013-07-29T12:29:48.683 回答
0

几周前我在java中设计了一个这样的算法。我使用了宽度为 N 的二进制矩阵，其中 N 是不同成本的数量，高度为 2^N，为我们提供了所有可能的组合。

因此，第一项将指的是您的情况下的最低成本。这是一个 1000、3000、4000 的例子。（你可以扩展它，但我只是想告诉你我是怎么做的。）

宽度 = N = 3

高度 = 2^N = 8

0 0 0 = 0       +   0       +   0       =   0
1 0 0 = 1000    +   0       +   0       =   1000
0 1 0 = 0       +   3000    +   0       =   3000
1 1 0 = 1000    +   3000    +   0       =   4000
0 0 1 = 0       +   0       +   4000    =   4000
1 0 1 = 1000    +   0       +   4000    =   5000
0 1 1 = 0       +   3000    +   4000    =   7000
1 1 1 = 1000    +   3000    +   4000    =   8000

我有一张清单，里面有费用。当我逐行遍历矩阵时，我只是检查了矩阵上有 1 的列表。由于对成本进行了排序，因此我发现等于或大于总金额的行将是最低的。

不明白的告诉我，我会详细说明！

于 2013-07-29T12:53:56.010 回答