5

この問題で使用される可能性のあるサブセット合計を生成するプログラムを作成しました。

$1 コインが 3 枚、$2 コインが 2 枚、$5 コインが 3 枚、$10 コインが 1 枚あるとします。これらのコインから $10 を得る方法は 4 つあります。$X1 コインが n1 枚、$X2 コインが n2 枚.... nm $Xm 枚ある場合、これらの限られた数のコインから $X を取得するには、何通りの方法がありますか?

{ X1, X1..... X1, X2, X2.......... X2, ..., ..., ........... .., Xm, Xm... Xm} を実行し、サブセットの合計を実行すると、確かに $X の結果が得られます。しかし、セット {n1, n2, n3.... nm} 、 {X1, X2, X3.... Xm} を使用する方法が見つかりませんでした。ナップザック問題の一種だと友達に言われましたが、どうしてかはわかりません。

これは私が書いたものの部分的なコードです:

ways[0]=1, mylim=0;
for(i=0;i<count;i++){
    if(mylim+coins[i]<=LIMIT) mylim+=coins[i];
    else mylim=LIMIT;

    for(j=mylim; j>=coins[i];j--){
        ways[j]=(ways[j]+ways[j-coins[i]])%MOD;
    }
}

もう少し丁寧に説明していただけると助かります。

編集:この質問は、コンピューター サイエンスの stackexchange に適していますが、私の古い質問なので、ここで編集しています。

この問題は、包含除外の原則で解決できます。コインの値は固定されているが、各コインの数はクエリごとに異なる場合に便利です。

way [v]が$x1、$x2、.. $xmで$vを作成する方法であり、それぞれが必要な回数だけ使用されるとします。ここで、 $x1 の n1 個のみを使用している場合、少なくとも( n1 + 1) 個の $x1 (実際には [ v - (n1 + 1)x1 ] の方法) を使用して構成を減算する必要があります。さらに、$x2のn2個だけを使用している場合は、ウェイ[ v - (n2 + 1)x2 ] も減算する必要があります。

ここで、少なくとも ( n1 + 1) $x1および ( n2 + 1) $x2が使用される構成を 2 回減算したため、ウェイを追加する必要があります[ v -(n1 + 1)x1 - (n2 + 1) x2 ] など

特に、

N = すべてのコインができるだけ多く使用される構成のセット、

Ai = 1 <= i <= mの場合、少なくともni + 1 個の$xiが使用される構成のセット

求めている結果 = | ん| - | A1 | - | A2 | .. - | 午前| + | A1とA2 | + | A1とA3 | + ... - | A1とA2とA3 | .....

無制限のコインで構成の数を計算するコードは、実際にはより単純です。

ways[0]=1;
for( int i = 0 ; i < count ; i++){
    for( int j = coins[i] ; j < ways.size() ; j++ ){
        ways[j] += ways[j-coins[i]];
    }
}
4

2 に答える 2

4

niあなたのすべてがであると仮定しましょう1。

しましょうways[j] = number of ways of obtaining sum j。

これはそのように計算できます（これはあなたがしていることですが、なぜ変数に名前を付けたのかわかりませんprimes）。

ways[0] = 1
for i = 1 to m do
    for j = myLim downto X[i] do
        ways[j] += ways[j - X[i]];

これは、価値のある各コインをXi1回だけ使用することを意味します。niただし、別のループを追加して、少なくとも1回、ほとんどの場合に使用できます。

ways[0] = 1
for i = 1 to m do
    for times = 1 to n[i] do // use Xi one time, then two times, then three, ..., then ni
        for j = myLim downto times*X[i] do
            ways[j] += ways[j - times*X[i]];

モジュロを適用して制限を計算することはできますが、簡単にするために省略しました。

于 2010-11-16T21:22:10.297 に答える
-4

この問題は「コイン問題」と呼ばれ、NP 困難であることが知られています。

ここでそれについて少し学ぶことができ ます。

于 2010-11-16T20:08:34.323 に答える