动态规划dp算法经典包子凑数java

目录
题目 包子凑数
动态规划思想
具体代码
__
题目 包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有NN种蒸笼，其中第ii种蒸笼恰好能放A_iAi个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买XX个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有XX个包子。比如一共有33种蒸笼，分别能放3、43、4和55个包子。当顾客想买1111个包子时，大叔就会选22笼33个的再加11笼55个的（也可能选出11笼33个的再加22笼44个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有33种蒸笼，分别能放4、54、5和66个包子。而顾客想买77个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
2
4
5
输出
一个整数代表答案。如果凑不出的数目有无限多个，输出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[]数据进行更新。
具体代码

1. import java.util.Scanner;
3. public class _包子凑数 {
4. public static void main(String[] args) {
5. Scanner scanner = new Scanner(System.in);
6. int n = scanner.nextInt();//N种蒸笼
7. int yueshu = 0;//最大公约数
8. int[] arr = new int[n + 1];//以下N行每行包含一个整数Ai
9. boolean[] dp = new boolean[10000];//下标index表示index个包子是否能够凑出
10. dp[0] = true;//默认0个包子可以凑出来
11. //在录入数据的同时，即可对dp[index]index个包子是否能够凑出来进行更新处理。
12. for (int i = 1; i <= n; i++) {
13. arr[i] = scanner.nextInt();//录入数据
14. /**
15. • 下面if-else语句动态求输入的数据的最大公约数
16. • 求当前第i种蒸笼恰好能放Ai个包子和前一个蒸笼能放的包子个数的最大公约数
17. */
18. if (i == 1)
19. yueshu = arr[1];
20. else
21. yueshu = yue(arr[i], yueshu);
22. //更新dp[]数组
23. for (int j = 0; j < 10000; j++) {
24. /**
25. • 如果dp[j]，即j个包子能够凑出来，
26. • 那么j个包子+第i种蒸笼恰好能放Ai个包子：arr[i]也能够凑出来
27. • 即index=(j+arr[i])个包子也能够凑出来。
28. */
29. if (dp[j])
30. dp[j + arr[i]] = true;//向后递推，动态规划的体现
31. }
32. }
33. //当最大公约数！=1 说明Ai不互质，则有无限个包子数凑不出来
34. if (yueshu != 1)
35. System.out.println("INF");
36. else {
37. //否则统计个数
38. int sum = 0;
39. for (int i = 0; i < dp.length; i++) {
40. if (!dp[i])
41. sum++;
42. }
43. System.out.println(sum);
44. }
45. }
46. /**
47. • 辗转相除法求a，b两个数的最大公约数
48. • @param a
49. • @param b
50. • @return
51. */
52. public static int yue(int a, int b) {
53. if (b == 0)
54. return a;
55. else
56. return yue(b, a % b);
57. }
58. }