0

引数として渡される特定の量になる最小の数値グループを見つけることを期待して、配列として与えられた数値のすべての可能な組み合わせを探索する関数を作成しようとしています。

これが私が行ってきたことです。これは、すべてのケースではなく一部のケースで機能しているようです。

数値を選択し、合計から減算し、配列の制限をそのままにして、新しい合計を関数に渡します。これにより、数値を再選択するオプションが与え
られ、2 番目の呼び出しで新しい合計を渡します。 、つまり、合計から現在選択されている数値を引いたものですが、配列を1つ小さくします。つまり、同じ数値を再度選択することはありません。

ただし、すべての選択肢をカバーしているわけではないことに気付きました。いずれにせよ、ソリューションには任意の数が不可欠であると想定しているためですが、3 番目のオプションをカバーするためにどの引数を渡せばよいかわかりません。 、これは数を選択していない、つまり合計から減算されていないことを意味し、配列のサイズを縮小しています。

あなたの助けは大歓迎です.ところで、私はCで書いています.

    int howManyCoins(int*coins,int size,int sum)
{
    return howManyCoins_aux(coins,size,sum,size-1);
}

int howManyCoins_aux(int*coins,int size, int sum,int chosen)
{
    if (sum==0)return 1;
    if (sum<0)return 0;
    if (chosen==0) return 0;
    if (coins[chosen]>sum) return 0;
    int res1=0,res2=0,best_solution=0;
    for (int i=chosen;i>=0;i--)
    {
        res1+=howManyCoins_aux(coins,size,sum-coins[i],chosen);
        res2+=howManyCoins_aux(coins,size,sum-coins[i],chosen-1);
        if(!(res1+res2)) best_solution=0;
        else if (res1==0) best_solution=res2;
        else if (res2==0) best_solution=res1;
        else best_solution=res2>res1?res1:res2;
    }
    return best_solution;
}
4

3 に答える 3

0

選択を次のように簡略化できます。コインを選択してコインを再選択できるか、コインを選択しないか（再帰はすべてのオプションをカバーします）

交換：

res1+=howManyCoins_aux(coins,size,sum-coins[i],chosen);
res2+=howManyCoins_aux(coins,size,sum-coins[i],chosen-1);

と

res1 = howManyCoins_aux(coins, size, sum-coins[i], chosen);
res2 = howManyCoins_aux(coins, size, sum, chosen-1);

各コインを1枚しか選べない場合:(これは変更の問題です）

res1 = howManyCoins_aux(coins, size, sum-coins[i], chosen-1);
res2 = howManyCoins_aux(coins, size, sum, chosen-1);

あなたのアルゴリズムはやや不明確で、繰り返しが多いと思います。forループを取り除き、関数を次のようなものに変更できます:(テストされていない）

int howManyCoins_aux(int *coins, int size, int sum, int chosen, int pos)
{
  if (sum == 0) return chosen;
  if (sum < 0 || pos == size) return 9999999;
  int res1 = 9999999;
  if (coins[pos] >= sum)
    res1 = howManyCoins_aux(coins, size, sum-coins[pos], chosen+1, pos);
  int res2 = howManyCoins_aux(coins, size, sum, chosen, pos+1);
  return min(res1, res2);
}

そうは言っても、再帰はおそらく進むべき道ではありません（小さなデータセットであっても、非常に長い時間がかかります）。整数計画法のように聞こえます。リンクでそれを解決するためのいくつかのオプションがあります。

于 2013-01-29T06:55:57.910 に答える
0

これはサブセット和問題の変種のように思えます。正の数のみを考慮しているため、ここで説明したような動的計画法のアプローチは、別のデータ構造を保持して、それぞれの可能な値を合計する数のセットを追跡する場合に機能する可能性があります。

于 2013-01-30T03:35:28.173 に答える
0

可能なすべての値を確認したい場合は、ビット配列を使用できます。指定された配列が十分に短い場合は、整数 (または長整数) をビット配列として使用できます。ここで、配列を a とすると、インデックス n ごとに、ビット配列のビット n のみが設定されている場合、a[n] が組み合わせになります。

于 2013-01-29T06:36:45.317 に答える