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

题目 包子凑数 动态规划思想 具体代码 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有NN种蒸笼,…

题目 包子凑数

动态规划思想

具体代码

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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[]数据进行更新。

具体代码

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/8049.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部