pku 1276?Cash Machine

http://poj.org/problem?id=1276

題意：

自動取款機里面的最大存錢量為cash，現在有n種不同價值的紙幣，每個都有一定的數量，問這些紙幣能夠組合出來的小于等于cash的最大值。

思路：

典型的多重背包，轉換01思想的做法TLE，只能用二進制倍增優化。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 1000007 #define N 12 using namespace std; //freopen("din.txt","r",stdin);int c[N],n[N]; int f[M];void zb(int c,int V){for (int i = V; i >= c; --i)f[i] = f[i]|f[i - c]; } void cb(int c,int V){for (int i = c; i <= V; ++i)f[i] = f[i]|f[i - c]; } int main(){//freopen("din.txt","r",stdin);int cash;int i,ni;while (~scanf("%d",&cash)){scanf("%d",&ni);for (i = 0; i < ni; ++i){scanf("%d%d",&n[i],&c[i]);}CL(f,0); f[0] = 1;for (i = 0; i < ni; ++i){if (n[i]*c[i] > cash){cb(c[i],cash);}else{int k = 1;while (k < n[i]){zb(k*c[i],cash);n[i] -= k;k <<= 1;}zb(n[i]*c[i],cash);}}for (i = cash; i >= 0; --i) if (f[i]) break;printf("%d\n",i);}return 0; }

?

pku 1014?Dividing

http://poj.org/problem?id=1014

題意：

有六種大理石，他們對應的價值分別為1,2,3,4,5,6. 給出每種大理石的個數，問我們是否能夠將他們等分成價值相等的兩份。

思路：

完全背包+二進制倍增優化。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 5000007 #define N 7 using namespace std; //freopen("din.txt","r",stdin);int f[M]; int c[N];void zb(int c,int V){for (int i = V; i >= c; --i)f[i] |= f[i - c]; } void cb(int c,int V){for (int i = c; i <= V; ++i)f[i] |= f[i - c]; } int main(){//freopen("din.txt","r",stdin);int i;int cas = 1;while (~scanf("%d%d%d%d%d%d",&c[0],&c[1],&c[2],&c[3],&c[4],&c[5])){if (!c[0] && !c[1] && !c[2] && !c[3] && !c[4] && !c[5]) break;printf("Collection #%d:\n",cas++);int V = 0;for (i = 0; i < 6; ++i) V += c[i]*(i + 1);if (V&1){puts("Can't be divided.");printf("\n");continue;}V /= 2;for (i = 0; i <= V; ++i) f[i] = 0;f[0] = 1;for (i = 0; i < 6; ++i){if (c[i]*(i + 1) > V)cb(i + 1,V);else{int k = 1;while (k < c[i]){zb(k*(i + 1),V);c[i] -= k;k <<= 1;}zb(c[i]*(i + 1),V);}}//printf("%d %d\n",V,f[V]);if (f[V]) puts("Can be divided.");else puts("Can't be divided.");printf("\n");}return 0; }

?

pku 2392?Space Elevator 可行性判斷+貪心

http://poj.org/problem?id=2392

題意：

奶牛想上太空給頂n種梯子，每種梯子對應三個值，a,h,c，a表示這種梯子必須在小于等于a的高度內使用，h表示它的高度，c表示這種梯子的個數。問內牛能夠累出的最大高度。

思路：

O（N*V）可行性判斷+按a從小到大貪心選擇

View Code

?pku 1742?Coins

http://poj.org/problem?id=1742

題意：

.有n中面值不同的硬幣，他們的價值，數量非別給出，求他們能夠組合出來的小于等于m的價值數；

思路：

樓爺的經典題目，多重背包可行性優化O（N*V）

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 100007 #define N 107 using namespace std; //freopen("din.txt","r",stdin);int f[M],c[N],w[N]; int cnt[M];int main(){//freopen("din.txt","r",stdin);int i,j;int n,m;while (~scanf("%d%d",&n,&m)){if (!n && !m) break;for (i = 0; i < n; ++i) scanf("%d",&w[i]);for (i = 0; i < n; ++i) scanf("%d",&c[i]);for (i = 0; i <= m; ++i) f[i] = 0;f[0] = 1;int ans = 0;for (i = 0; i < n; ++i){for (j = 0; j <= m; ++j) cnt[j] = 0;for (j = 0; j <= m - w[i]; ++j){if (f[j] && !f[j + w[i]] && cnt[j] < c[i]){f[j + w[i]] = 1;cnt[j + w[i]] = cnt[j] + 1;ans++;}}}printf("%d\n",ans);} }

?pku 1787?Charlie's Change (zoj2156)

http://poj.org/problem?id=1787? 多重背包記錄選擇的物品的個數

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1156

題意：

有面值為1,5,10,20的四種硬幣，非別給出他們的數量問他是否能夠組合出面值為P的價值，若果可以輸出他的方案，如果存在多種方案輸出使用硬幣數最多的。

思路：

O（N*V）優化多重背包的可行性求解，這里主要是開一個二維數組num[i][j]表示i狀態下裝了第j中硬幣多少個。

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 10007 #define N 4 using namespace std; //freopen("din.txt","r",stdin);int f[M],num[M][N]; int c[N],cnt[M]; int val[4] = {1,5,10,25}; int main(){//freopen("din.txt","r",stdin);int V,i,j;while (~scanf("%d%d%d%d%d",&V,&c[0],&c[1],&c[2],&c[3])){if (!V && !c[0] && !c[1] && !c[2] && !c[3]) break;CL(num,0);for (i = 0; i <= V; ++i) f[i] = 0;f[0] = 1;for (i = 0; i < 4; ++i){for (j = 0; j <= V; ++j) cnt[j] = 0;for (j = 0; j <= V - val[i]; ++j){if (f[j] && cnt[j] < c[i]){int a = j + val[i];if (!f[a]){f[a] = 1;cnt[a] = cnt[j] + 1;//將上一個狀態轉移下來for (int k = 0; k < 4; ++k){num[a][k] = num[j][k];}num[a][i]++;}else{int s1 = 0,s2 = 0;for (int k = 0; k < 4; ++k){s1 += num[j][k];s2 += num[a][k];}//存在多種方案去最大的if (s2 < s1 + 1){for (int k = 0; k < 4; ++k){num[a][k] = num[j][k];}num[a][i]++;}}}}}if (f[V]){printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",num[V][0],num[V][1],num[V][2],num[V][3]);}else{puts("Charlie cannot buy coffee.");}}return 0; }

?

更新中.......

轉載于:https://www.cnblogs.com/E-star/archive/2012/10/10/2718761.html

總結

以上是生活随笔為你收集整理的多重背包题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。