完全背包即物品的數(shù)量不收限制，

根據(jù)01背包的思想，因?yàn)槊考锲分荒苓x1個(gè)，則要求我們不能依賴已選擇物品i的選項(xiàng)的時(shí)候，所以需要逆序遍歷

則在完全背包問題中，我們需要正序遍歷。

此題時(shí)要求求出最小價(jià)值。

代碼如下：

#include <stdio.h> #include <algorithm> using namespace std; #define inf 10000000 #define min(a,b) a<b?a:b int dp[11000]; int p[600]; int w[600];int main() {int i,j,k,n,e,f;scanf("%d",&k);while(k--){scanf("%d",&e);scanf("%d",&f);int diff = f - e;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&p[i]);scanf("%d",&w[i]);}//memset(dp,inf,sizeof(dp));//不可以這樣初始化for(int i=0;i<=diff;i++) { dp[i]=inf; } dp[0] = 0;for(i=1;i<=n;i++){for(j=w[i];j<=diff;j++){ dp[j] = min(dp[j],dp[j-w[i]]+p[i]); }}if(dp[diff] == inf){printf("This is impossible.\n");}else{printf("The minimum amount of money in the piggy-bank is %d.\n",dp[diff]);}} system("pause");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/yueyanglou/p/5354757.html

總結(jié)

以上是生活随笔為你收集整理的完全背包问题 POJ1384的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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