18

N 個のコインのリスト、それらの値 (V1、V2、...、VN)、および合計 S が与えられます。合計が S であるコインの最小数を見つけます (1 つのタイプのコインをいくつでも使用できます)。または、合計が S になるような方法でコインを選択することは不可能であると報告します。

動的計画法を理解しようとしていますが、理解していません。与えられた説明が理解できないので、このタスクをプログラムする方法のヒントをいくつか教えていただけませんか? コードはありません。どこから始めるべきかのアイデアだけです。

ありがとう。

4

12 に答える 12

11

この問題に対する正確な答えは、ここでよく説明されています。 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

于 2011-05-07T02:10:55.597 に答える
6

これは古典的なナップザックの問題です。詳細については、こちらを参照してください:ウィキペディアのナップザックの問題

また、いくつかの並べ替え、特に最大値から最小値への並べ替えも確認する必要があります。

于 2010-11-22T16:31:17.917 に答える
3

すでに指摘したように、この問題には動的計画法が最適です。私はこれのために Python プログラムを書きました:-

def sumtototal(total, coins_list):
    s = [0]
    for i in range(1, total+1):
        s.append(-1)
        for coin_val in coins_list:
            if i-coin_val >=0 and s[i-coin_val] != -1 and (s[i] > s[i-coin_val] or s[i] == -1):
                s[i] = 1 + s[i-coin_val]

    print s
    return s[total]

total = input()
coins_list = map(int, raw_input().split(' '))
print sumtototal(total, coins_list)

入力用:

12 2 3 5

出力は次のようになります。

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 list_index は必要な合計であり、list_index の値は no です。その合計を得るために必要なコインの。上記の入力 (値 12 を取得) の答えは 3 (値 5、5、2 のコイン) です。

于 2014-04-13T19:08:23.687 に答える
2

あなたが望むアプローチは次のようなものだと思います：

sum を生成したいことがわかっていますS。生産する唯一の方法Sは、最初に生産S-V1し、次に価値のあるコインを追加することV1です。またはS-V2、価値のあるコインを作成して追加しますV2。また...

次に、T=S-V1、T-V1またはT-V2、または...

このように後退することで、SあなたVの s から生産するための最善の方法を決定することができます。

于 2010-11-22T16:36:13.377 に答える
1

質問には既に回答がありますが、誰かの役に立てば、私が書いた実用的な C コードを提供したいと思いました。enter code here

コードにはハードコードされた入力がありますが、単純にするためです。最終的な解決策は、各合計に必要なコインの数を含む配列 min です。

#include"stdio.h"
#include<string.h>

int min[12] = {100};
int coin[3] = {1, 3, 5};

void
findMin (int sum) 
{
    int i = 0; int j=0;
    min [0] = 0; 

    for (i = 1; i <= sum; i++) {
        /* Find solution for Sum = 0..Sum = Sum -1, Sum, i represents sum
         * at each stage */
        for (j=0; j<= 2; j++) {
            /* Go over each coin that is lesser than the sum at this stage
             * i.e. sum = i */
            if (coin[j] <= i) {
                if ((1 + min[(i - coin[j])]) <= min[i]) { 
                    /* E.g. if coin has value 2, then for sum i = 5, we are 
                     * looking at min[3] */
                    min[i] = 1 + min[(i-coin[j])]; 
                    printf("\nsetting min[%d] %d",i, min[i]);
                }
            }
        }
    }
}
void
initializeMin()
{
    int i =0;
    for (i=0; i< 12; i++) {
        min[i] = 100;
    }
}
void
dumpMin() 
{
    int i =0;
    for (i=0; i< 12; i++) {
        printf("\n Min[%d]: %d", i, min[i]);
    }
}
int main() 
{
    initializeMin();
    findMin(11);
    dumpMin(); 
}
于 2014-09-14T05:18:33.250 に答える
0

動的計画法についてはわかりませんが、これが私のやり方です。ゼロから始めて、あなたの道を歩んでくださいS。1 コインでセットを作成し、そのセットで 2 コイン セットを作成する、というように... を検索しS、 より大きいすべての値を無視しますS。各値について、使用したコインの数を覚えておいてください。

于 2010-11-22T16:45:12.780 に答える