我一直在使用动态规划来解决硬币找零问题。我尝试创建一个数组 fin[],其中包含该索引所需的最小硬币数量,然后打印它。
我编写了一段代码,我认为应该给出正确的输出,但我不明白为什么它没有给出准确的答案。
例如:对于输入:4 3 1 2 3(4是要找的金额,3是可用硬币的种类数量,1 2 3是硬币价值列表)输出应该是: 0 1 1 1 2 (因为我们有 1,2,3 可用硬币,所以需要 0 个硬币来兑换 0,1 个硬币来兑换 1,1 个硬币来兑换 2,1 个硬币来兑换 3 和 2兑换硬币 4)
但它给出 0 1 2 2 2
这是代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in= new Scanner(System.in);
int ch = in.nextInt();
int noc = in.nextInt();
int[] ca = new int[noc];
for(int i=0;i<noc;i++)
{
//taking input for coins available say a,b,c
ca[i] = in.nextInt();
}
int[] fin = new int[ch+1]; //creating an array for 0 to change store the minimum number of coins required for each term at index
int b=ch+1;
for(int i=0;i<b;i++)
{
int count = i; //This initializes the min coins to that number so it is never greater than that number itself. (but I have a doubt here: what if we don't have 1 in coins available
for(int j=0; j<noc; j++)
{
int c = ca[j]; //this takes the value of coins available from starting everytime i changes
if((c < i) && (fin[i-c] +1 < count)) // as we using dynamic programming it starts from base case, so the best value for each number i is stored in fin[] , when we check for number i+1, it checks best case for the previous numbers.
count = fin[i-c]+1 ;
}
fin[i]= count;
}
for(int i=0;i<b;i++)
{
System.out.println(fin[i]);
}
}
}
我从这个页面引用了:http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html
有人可以帮忙吗?
The article http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html您引用的,很好地解释了如何使用动态编程构建硬币兑换器算法。该算法的Python版本可以翻译成Java:
import java.util.Arrays;
import java.util.List;
public class CoinChanger {
public int[] dpMakeChange(List<Integer> coinValueList, int change, int[] minCoins) {
for (int cents = 0; cents <= change; cents++) {
int coinCount = cents;
for (Integer c : coinValueList) {
if (c > cents) {
continue;
}
if (minCoins[cents - c] + 1 < coinCount) {
coinCount = minCoins[cents - c] + 1;
}
}
minCoins[cents] = coinCount;
}
return minCoins;
}
public static void main(String[] args) {
List<Integer> coinValueList = Arrays.asList(new Integer[]{1, 2, 3});
int change = 10;
int[] minCoins = new int[change + 1];
int[] result = (new CoinChanger()).dpMakeChange(coinValueList, change, minCoins);
for (int i = 0; i < result.length; i++) {
System.out.println("For change = " + i + " number of coins = " + result[i]);
}
}
}
正如您的问题一样,使用价值 1、2 和 3 的硬币,之前的算法会为您提供正确的值:
For change = 0 number of coins = 0
For change = 1 number of coins = 1
For change = 2 number of coins = 1
For change = 3 number of coins = 1
For change = 4 number of coins = 2
For change = 5 number of coins = 2
For change = 6 number of coins = 2
For change = 7 number of coins = 3
For change = 8 number of coins = 3
For change = 9 number of coins = 3
For change = 10 number of coins = 4
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)