0

特定の金種のコインが与えられた場合に、変更するコインの最大数を見つけたいというこの問題を解決しようとしていました。

例 たとえば、価値が 3 と 5 のコインが与えられ、15 に両替したい場合、解決策は {3,3,3,3,3} になります (指摘してくれた JoSSte に感謝します) 同様に、値が 3 と 5 のコインで、7 に両替したい場合は、「解決できません」と表示する必要があります

次のように、最小数のコインを見つけるためにこれを行うことができました

import java.util.ArrayList;
import java.util.Arrays;


public class Minimum
{
    static int[] options = {5,3};

    public static void main(String[] args)
    {
        ArrayList<Integer> result = new ArrayList<Integer>();

        result = fun(15);
        if(result.size() == 999)
             System.out.println("Not possible to make change with this denomination");
        else 
        {
            for(int i = 0;i<result.size();i++)
                System.out.print(result.get(i));
        }
    }

    static ArrayList<Integer> fun(int n)
    {       
        if(n == 0)
        {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }
}

if(n<0) と呼ばれるチェックがあることに注意してください。合計にならない組み合わせは、そのサイズを最小値にできない非常に大きな数に設定することによってオプションから削除されます。

ただし、上記を変更してコインの最大数を見つけるにはどうすればよいですか

4

2 に答える 2

0

これは、C ++でのコイン変更dpコードです。

int coin[] = {3, 5}; //initialize array
int make;
int dp[2][100];

int call(int i, int amount)
{
     if(i >= 2) { // All coins have been taken
          if(amount == make) return 1;
          return 0;
     }

     if(dp[i][amount] != -1) return dp[i][amount];
     int ret1 = 0, ret2 = 0;
     // try to take coin i
     if(amount + coin[i] <= make) ret1 = call(i, amount + coin[i]); 

     ret2 = call(i+1, amount); // don't take coin i
     return dp[i][amount] = ret1 | ret2; // is possible or not?
}

int main()
{
    make = 7;
    memset(dp, -1, sizeof(dp));
    if(call(0, 0) == 0) cout << "not possible" << endl;
    else cout << "possible" << endl;

    return 0;
}
于 2015-09-22T22:26:40.387 に答える