0

次の問題を解決するアルゴリズムを探しています（例を挙げて説明します）：

利用可能な金額が 10.000 $ あり、次の費用が自分の金額を使用して資金調達できるとします。

コスト 1: 1.000 $

コスト 2: 3.000 $

コスト 3: 4.000 $

コスト 4: 5.000 $

費用は部分的に支払うことはできないため、全額を支払うか、まったく支払わないかのいずれかになります。私が探しているのは、利用可能な金額を超えないコストの組み合わせを見つけるのに役立つアルゴリズムですが、反対側では利用可能な金額の大部分または全部を使用します。

私の例では、コスト 1 + コスト 3 + コスト 4 になります。

また、最大限に融資できる費用の数を決定するパラメーターも追加したいと思います。この例で 2 つのコストしか支払うことができないと言うと、コスト 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

予算がなくなるまで、リストを並べ替えて一番上を選ぶことができます。ビンパッキングでも使用され、最適な範囲内にあることが保証されています。

于 2013-07-29T12:29:48.683 に答える
0

あなたの問題はNP 問題です。許容できる時間枠内で最適なソリューションを見つけることを保証する、この問題に対する既知のソリューションはありません。最適なソリューションを実際に見つける唯一の方法は、考えられるすべてのソリューションを試してから、どれが最適かを確認することです。ただし、何千ものコストがある場合、もちろん、これは非常に遅くなります。

上記の単純なアプローチよりも高速な他のすべてのソリューションは、最適なソリューションを見つけることが保証されていません。彼らは良い解決策を見つけるかもしれませんが、より良い解決策が可能であったかどうかを確実に言うことはできません.

次の問題と同じです。 X ポンドの商品を輸送できるトラックがあり、さまざまな重量の商品があります。目標は、使用可能な容量を最適に使用することです。これは「ナップザック問題」とも呼ばれます。このページにリストされているもの以外に、既知のより良い解決策はありません。ただし、最適な結果を保証できるものはありません。

于 2013-07-29T13:03:10.770 に答える