算法找到的元素最适合的一个特定量 [英] Algorithm to find elements best fitting in a particular amount

问题描述

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

I'm looking for an algorithm to solve the follwoing problem (I will explain it with an example):

让说，我有10.000 $可用量和成本之后，我可以用我的资金量：

Let say I have 10.000 $ available amount and following costs I can finance using my amount:

成本1：1.000 $

cost 1: 1.000 $

成本2：3.000 $

cost 2: 3.000 $

成本3：4.000 $

cost 3: 4.000 $

成本4：5.000 $

cost 4: 5.000 $

该费用不能被部分你付出的全部成本或您不支付它在所有付出了那么无论是。我所寻找的是一种算法，它可以帮助我找到的，不会超过可用金额的费用相结合，但在另一边使用最多的部分或全部可用量。

The costs cannot be paid partially so either you pay the whole cost or you don't pay it at all. What I am looking for is an algorithm which helps me find the combination of costs which will not exceed available amount, but on the other side use the most part or the whole available amount.

在我的例子将是：成本1 +费用3 +耗资40

In my example it would be: cost 1 + cost 3 + cost 4.

我还想加一个参数，它决定了多少成本可以最大限度地提供资金。如果我说在我的例子，只有两个成本可以支付最高费用3和4的成本将被退回。

I would like also to add an parameter which determines how many costs can be maximally financed. If I say in my example that only two costs can be payed, cost 3 and cost 4 will be returned.

我的方法是检查所有可用的组合，总结他们，并挑选其中最好使用可用量的之一。我不知道但是如果有一个simpliest的方式找到最​​佳组合。

My approach would be to check all available combinations, sum them and pick the one which best uses the available amount. I wonder however if there is a simpliest way to find the optimal combination.

推荐答案

这是一个简单的动态规划问题（背包的变化）。状态可以被定义为[位置] [rest_amount] [how_many_bills_can_be_paid]。下方的递归解决方案：

This is a simple dynamic programming problem (A variation of Knapsack). State can be defined as [position][rest_amount][how_many_bills_can_be_paid]. A recursive solution below:

假设 C 是成本的阵列和备忘录与-1初始化：

assuming Cis the array of cost and memo is initialized with -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;
}

这篇关于算法找到的元素最适合的一个特定量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！