正題

---

題目大意

n個(gè)物品，每個(gè)物品有$c_i$元，求有多少種方案數(shù)使得無(wú)法再買另外任何的東西。

---

解題思路

我們發(fā)現(xiàn)其實(shí)對(duì)于每種方案判斷只需要考慮剩下的最小的哪一個(gè)，所以我們可以將$c$從小到大排序。然后用$f_{i,j}$表示選擇了$1～i?1$還沒有選擇時(shí)，耗費(fèi)了j元的方案數(shù)。
動(dòng)態(tài)轉(zhuǎn)移:
$$f_{i,j}=f_{i+1,j+c_i}+f_{i+1,j}$$
最后我們枚舉最小沒有選擇的是$x$，還剩余$res$元
$$\sum _{r=0}^{c_x?1}{f}_{n,m?r}$$

---

code

#include<cstdio> #include<algorithm> #define N 2010 #define XJQ int(1e7+7) using namespace std; int n,m,c[N],f[N][N],ans,t; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&c[i]),ans+=c[i];if(ans<=m){printf("1");return 0;}ans=0;sort(c+1,c+1+n);//排序f[n+1][0]=1;//初始化for(int i=n;i>=1;i--)for(int j=0;j<=m;j++)f[i][j]=(f[i+1][j]+(j>=c[i]?f[i+1][j-c[i]]:0))%XJQ;//動(dòng)態(tài)轉(zhuǎn)移for(int i=1;i<=n;i++){for(int j=0;j<c[i];j++)if(m-t-j>=0)(ans+=f[i+1][m-t-j])%=XJQ;//計(jì)算答案t+=c[i];//減少剩余}printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的nssl1231-Gift【01背包,dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。