「5元硬币」动态规划，存在1元，3元，5元硬币若干，使用最少硬币构成n元

5元硬币

题目描述：存在一元，三元，五元硬币若干，如何用最少的硬币凑够11元。

看到最少这个字眼，我们可以进行判断能否通过动态规划进行求解，经过分析可以发现我们可以把这个问题拆分成相等的子问题，因此是可以用动态规划的：

假设f[n]等于构成n元的最少的硬币数,那么f[n]=f[n-m]+f[m]。

我们可以采用向上递推的方式求解问题，可以先归纳一下前五个情况（因为最大到5元）

我们容易发现：f[1]=1,f[2]=2,f[3]=1,f[4]=2,f[5]=1。

那么f[6]怎么算呢？容易发现，f[6]=min{f[1]+f[5],f[2]+f[4],f[3]+f[3]}

所以，对于f[n]我们只要通过上述方式即可求得。

代码如下：

import java.util.scanner;

public class Main2 {

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()) {
            int m = scanner.nextint();
            int f[] = new int[m + 1];
            f[1] = 1;
            f[2] = 2;
            f[3] = 1;
            f[4] = 2;
            f[5] = 1;

            for (int i = 6; i <= m; i++) {
                int min = 1000;
                for (int j = 1; j <= i / 2; j++) {
                    if (min > (f[j] + f[i - j])) {
                        min = f[j] + f[i - j];
                    }
                }
                f[i] = min;
            }

            System.out.println(f[m]);
        }
    }
}

测试几组数据试一下：

动态规划，存在1元，3元，5元硬币若干，使用最少硬币构成n元

5元硬币

相关阅读

栏目导航

推荐阅读

热门阅读