目录
题目 包子凑数
输入
输出
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
6
动态规划思想
在讲动态规划思想前，本题还使用到了经典数论Ax+By=C（x,y>0）问题：若A，B互质，则有无限个C时的方程无解。否则可能有解。推广到a,b,…,n同时成立。可以利用这个思想求是否有无穷个包子数凑不出来。
所以本题中可以类似的用a1,a2,…an表示能放的包子的个数，找到合适的x，y，…….n凑出C。如果方程有解则能凑出，否则不能凑出。至于求最大公约数可以利用辗转相除法求。
然后本题就可以类似背包问题，使用到一个boolean[] dp，下标index表示index个包子是否能够凑出。当dp[i] 即i个包子可以凑出的话，那么j个包子+第i种蒸笼恰好能放Ai个包子：arr[i]也能够凑出来即index=(j+arr[i])个包子也能够凑出来：dp[j + arr[i]] = true;动态规划的思想就体现在这，另外为了节省时间，在录入数据的同时，就可以对dp[]数据进行更新。
具体代码
import java.util.Scanner; public class _包子凑数 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();//N种蒸笼 int yueshu = 0;//最大公约数 int[] arr = new int[n + 1];//以下N行每行包含一个整数Ai boolean[] dp = new boolean[10000];//下标index表示index个包子是否能够凑出 dp[0] = true;//默认0个包子可以凑出来 //在录入数据的同时，即可对dp[index]index个包子是否能够凑出来进行更新处理。 for (int i = 1; i <= n; i++) { arr[i] = scanner.nextInt();//录入数据 / * 下面if-else语句动态求输入的数据的最大公约数 * 求当前第i种蒸笼恰好能放Ai个包子和前一个蒸笼能放的包子个数的最大公约数 */ if (i == 1) yueshu = arr[1]; else yueshu = yue(arr[i], yueshu); //更新dp[]数组 for (int j = 0; j < 10000; j++) { / * 如果dp[j]，即j个包子能够凑出来， * 那么j个包子+第i种蒸笼恰好能放Ai个包子：arr[i]也能够凑出来 * 即index=(j+arr[i])个包子也能够凑出来。 */ if (dp[j]) dp[j + arr[i]] = true;//向后递推，动态规划的体现 } } //当最大公约数！=1 说明Ai不互质，则有无限个包子数凑不出来 if (yueshu != 1) System.out.println("INF"); else { //否则统计个数 int sum = 0; for (int i = 0; i < dp.length; i++) { if (!dp[i]) sum++; } System.out.println(sum); } } / * 辗转相除法求a，b两个数的最大公约数 * @param a * @param b * @return */ public static int yue(int a, int b) { if (b == 0) return a; else return yue(b, a % b); } } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227376.html原文链接：https://javaforall.net
