我得到了这部分关于动态规划的代码(它找到了硬币找零的最佳组合。例如,如果我们有两个值(value) 3 和 4 的硬币 --> {3,4};以及我们要计算的金额想要改变的例子是 sum=11,答案是我们总共需要 3 个硬币(2 个硬币值 =4 和 1 个硬币值 =3)。下面的代码运行良好,但并不完全符合我的要求
我正在尝试对下面的代码进行逆向工程,以便它提供更清晰的答案,如下所示:
Total coins:3 , #of Coins with value "3" = 1, #of Coins with value "4" = 2
可以从这个数组 minimum[sum] 中找到给定数量的总硬币数。 但是我试图获得的其余信息(哪个硬币有什么值(value))似乎几乎不可能找到。同样从数组 coins[sum][0] 我只能找到最后使用的硬币,在这个例子中它是 3。
Inputs: sum=11 ,int[] valueCoins = new int[]{3,4};
Output:
1 10011 0(0)
2 10011 0(0)
3 1 3(0)
4 1 4(0)
5 10011 0(0)
6 2 3(3)
7 2 3(4)
8 2 4(4)
9 3 3(6)
10 3 3(7)
11 3 3(8)
如您所见,它会检查从 1 到 11 的所有内容,但当它到达 11 时,它会存储正确数量的硬币 (3) 和最后使用的硬币 (3)。
public class MinimumCoin {
public static void main(String args[]){
int[] valueCoins = new int[]{3,4};
int sum = 11;
int[] minimum = new int[sum+1];
int[][] coins = new int[sum+1][2];
/* initializing the minimum of every sum to infinity */
for(int i = 1; i < minimum.length; i++){
minimum[i] = sum + 10000;
}
/* initializing that for minumum sum of zero, 0 coin is required */
minimum[0] = 0;
for(int i = 1; i <= sum; i++){
for(int j = 0; j <valueCoins.length; j++){
if(valueCoins[j] == i){
minimum[i] = 1;
coins[i][0] = i;
coins[i][1] = 0;
}
else if((valueCoins[j] < i) && (((minimum[i-valueCoins[j]]) + 1) < minimum[i])){
minimum[i] = (minimum[i-valueCoins[j]]) + 1;
coins[i][0] = valueCoins[j];
coins[i][1] = (i-valueCoins[j]);
}
}
}
for(int k = 1; k < minimum.length; k++){
System.out.println( k + " " + minimum[k] + " " + coins[k][0] +"("+ coins[k][1] +")");
}
}
}
感谢任何输入!
~问候,S
最佳答案
问题是 coins
中的值是硬币的值,而不是计数。 硬币
:
0 0 0 3 0 0 3 3 4 3 3 3
0 0 0 0 4 0 3 4 4 6 7 8
因此您需要重建计数:
for(int k = 1; k < minimum.length; k++)
{
int count1 = 0, count2 = 0, pos = k;
if (coins[pos][1] > 0)
while (true)
{
if (coins[pos][0] == 3) count1++;
if (coins[pos][0] == 4) count2++;
if (coins[pos][1] == 3) count1++;
if (coins[pos][1] == 4) count2++;
if (coins[pos][1] < 5) // stop when 0/3/4
break;
pos = coins[pos][1];
}
System.out.println(k + " " + minimum[k] + " " +
count1 + " of coin 3, " + count2 + " of coin 4");
}
这些也是解决问题的选项:
每个硬币出现的次数都有行。如果您有 2 个硬币,每个硬币可以出现 5 次,那么您将有 5x2 = 10 行。
有如下行:
- 第 1 行 = 硬币 1 的第 1 行
- 第 2 行 = 硬币 2 的第 1 行
- 第 3 行 = 硬币 1 的第 2 行
- 第 4 行 = 硬币 2 的第 2 行
- 第 5 行 = 硬币 1 的第 4 行
- 第 6 行 = 硬币 2 的第 4 行
- 第 7 行 = 硬币 1 的第 8 行
- 第 8 行 = 硬币 2 的第 8
- ...
后者明显更复杂但更受欢迎,因为更多的硬币将有更少的行。
关于java - 动态换币算法(最优结果),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15039833/