JAVA中的货币金额和票据优化算法

Question

问题如下。我必须累积两套货币：300和200

纸币将仅为5的倍数。输入可以是任何货币票据，如：

20, 20, 25, 50, 40, 5, 40, 40, 40, 30, 25, 5, 50, 50, 40, 20, 25, 25, 25, 30, 20, 20, 20, 20, 45

可以有多个输出，如

Output1:{50, 40, 40, 40, 40, 40, 25, 25}, {50, 50, 30, 30, 20, 20}
Output2:{50, 50, 40, 40, 20, 40, 40, 20}, {50, 45, 25, 30, 25, 25}

如何使用java解决这个问题。似乎我需要应用动态规划方法，但我无法正确构造算法

注意：注释的数量是动态的。此外，未提及最大注释值。甚至可以是200或300

Answer 1

您可以这样设计->

bool dp(int _300, int _200, int cur){
    if(_300==0 and _200==0) return true;
    if(_300<0 or _200<0) return false;
    if(cur>=input.size()) return false;

    if(_300!=0) dp(_300-input[cur], _200, cur+1);
    if(_200!=0) dp(_300, _200-input[cur], cur+1);
    dp(_300, _200, cur);
}

我还没有完成memoization部分和printing output部分。但是，我想你可以自己做

当您知道存在有效输出时，可以从数组中打印它

希望有帮助：）