當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

01背包问题。

發布時間：2024/1/17 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了 01背包问题。小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

pku 3624?Charm Bracelet

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

最裸的01背包。

View Code #include <cstdio> #include <cstring> #include <iostream> #define CL(a,num) memset((a),(num),(sizeof(a))) #define N 3405 #define M 12888 using namespace std;int c[N],w[N]; int f[M];int main(){int i,j;int n,m;scanf("%d%d",&n,&m);for (i = 0; i < n; ++i){scanf("%d%d",&c[i],&w[i]);}CL(f,0);for (i = 0; i < n; ++i){for (j = m; j >= c[i]; --j){f[j] = max(f[j],f[j - c[i]] + w[i]);}}printf("%d\n",f[m]);return 0; }

pku 3628?Bookshelf 2

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

題意：

有n頭牛，他們都有各自的身高，有一個書架的高度為m，求這些牛能夠累加起來的大于等于m的最小高度。

思路：

這道題類似于樓爺的O（V*n）解多重背包時的思路，只不過這里不用記錄每個牛使用了多少次因為每個牛就一個。因為要保證每個僅使用一次所以V要逆序。就轉化成了01背包的形式。

暴力dfs選與不選可過。

pku 3211?Washing Clothes

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

題意：

Dearboy 和他的女朋友一起洗衣服，這些衣服分為n種顏色，總共有m件，每件衣服對應了一個洗刷需要的時間，他和他的女朋友可以同時洗，為了避免混色只有洗完了這種顏色的所有衣服后才能洗刷下一種顏色的衣服。問洗完所有衣服所需要的時間。

思路：

首先將每種衣服按顏色分類，然后求出每種顏色衣服洗刷所需的時間和sum[i]我們求出能夠盡量組合出來的小于等于sum[i]/2的最大值，然后求sum[i] - x即可。

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 100007 using namespace std; //freopen("din.txt","r",stdin);bool f[N]; char str[12][12]; int a[12][107]; int sum[12],p[12]; int n,m;int getnum(char *s){for (int i = 0; i < n; ++i){if (!strcmp(s,str[i])){return i;}} } int main(){int i,j,k;int val;char tpstr[12];while (~scanf("%d%d",&n,&m)){if (!n && !m) break;CL(p,0); CL(sum,0);for (i = 0; i < n; ++i) scanf("%s",str[i]);for (i = 0; i < m; ++i){scanf("%d%s",&val,tpstr);int num = getnum(tpstr);a[num][p[num]++] = val;sum[num] += val;}int ans = 0;for (i = 0; i < n; ++i){for (j = 0; j <= sum[i]; ++j) f[j] = 0;f[0] = 1;for (j = 0; j < p[i]; ++j){for (k = sum[i]/2 - a[i][j]; k >= 0; --k){if (f[k])f[k + a[i][j]] = 1;}}for (j = sum[i]/2; j >= 0; --j)if (f[j]) break;ans += (sum[i] - j);}printf("%d\n",ans);}return 0; }

pku 1745?Divisibility

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

題意：

給你n個數，這n個數的值的取值為<|1000|,添加n-1個加號或者-問得到的值中是否存在能夠整除K的值。

思路：

其實也不是嚴格的01背包了，只是思想類似，首先是同余的應用(a +b)%m ?= (a%m + b%m)%m

由于m<=100所以就將數壓縮到0-100了，dp[i][j]表示前i個數是否可以形成j這個數。我們只要往背包里塞，看是否能夠得到0這個值就好了。注意這里負數區域的處理

-7%3 = 2

View Code #include <cstdio> #include <cstring> #include <iostream> #define CL(a,num) memset((a),(num),(sizeof(a))) #define N 10007 #define M 107 using namespace std;int dp[N][M]; int a[N]; int n,m; //這里來處理負數取余 int MOD(int val,int mod){if (val%mod == 0) return 0;else{if (val > 0) return val%mod;else{val = -val;return (mod*(val/mod + 1) - val);}} } int main(){int i,j;scanf("%d%d",&n,&m);for (i = 1; i <= n; ++i){scanf("%d",&a[i]);a[i] = MOD(a[i],m);}CL(dp,0);dp[0][0] = 1;int tmp;for (i = 1; i <= n; ++i){for (j = 0; j < m; ++j){if (dp[i - 1][j]){tmp = MOD(j + a[i],m);dp[i][tmp] = 1;tmp = MOD(j - a[i],m);dp[i][tmp] = 1;}}}if (dp[n][0]) puts("Divisible");else puts("Not divisible");return 0; }

pku 1976?A Mini Locomotive 01背包裝+連續線段長度

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

題意：

有三個火車頭，n個車廂，每個車廂里面對應的有一定的人數。規定每個火車頭最多拉m個連續的車廂而且他們拉的車廂一定是從左到右連續的，問它能夠拉的最多的人數；

思路：

類似01背包的解法，首先每個火車最多拉m個連續的車廂，這里我們把只要存在連續的m個車廂的就看成一個物品。相當于往背包容量為3的背包里面放物品所得的最大價值量。但是這里注意每連續的m個車廂為一個物品，f[i][j] = max(f[i - 1][j],f[i - m][j - 1] + sum[i] - sum[i - m]); 這里對于每個物品要么不放，要么就是放（放連續的m個車廂）

sum[i] = a[0] + a[1] + ... ?+ a[i];

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 207 #define N 50007 using namespace std; //freopen("din.txt","r",stdin);int f[N][4]; int a[N],sum[N];int main(){//freopen("din.txt","r",stdin);int T,i,j;int n,m;scanf("%d",&T);while (T--){scanf("%d",&n);sum[0] = 0;for (i = 1; i <= n; ++i){scanf("%d",&a[i]);sum[i] = sum[i - 1] + a[i];}scanf("%d",&m);CL(f,0);for (i = 1; i <= n; ++i){for (j = 1; j <= 3; ++j){int tp = i - m;if (tp < 0) tp = 0;//因為最多是m個車廂，當不足是我們可以選擇拉小于m個的車廂f[i][j] = max(f[i - 1][j],f[tp][j - 1] + sum[i] - sum[tp]);}}printf("%d\n",f[n][3]);}return 0; }

?pku 2923?Relocation 狀態壓縮+01背包裝狀態

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

題意：

用兩輛車搬家，每輛車都有各自的載重量c1,c2如果超過他的載重量汽車就完蛋。有n個家具每個家具都有各自的重量，這里保證每個家具肯定能夠用其中一輛車運走，即wi < max(c1,c2);

問最少需要多少次搬運將所有家具運完。

思路：

前邊起初做的背包是往背包里面放物品，后來是放長度為m的連續的線段，而這里又成了放某種狀態，感嘆背包偉大啊。。。。

首先將所有狀態中的能夠一次用c1,c2運走的狀態都選出來，選的過程還是利用01背包來組合出最大的小于等于c1的運輸量，然后判斷c2是否可以。然后利用01背包將選出的狀態往背包容量為最終狀態的MSK里面放記錄最小次數即可。

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 1027 #define N 15 using namespace std; //freopen("din.txt","r",stdin);int f[M]; int msk[M]; int a[N],n; int c1,c2;bool isok(int x){int sum = 0,i,j;for (i = 0; i <= c1; ++i) f[i] = 0;f[0] = 1;for (i = 0; i < n; ++i){if (x&(1<<i)){sum += a[i];for (j = c1; j >= a[i]; --j){if (!f[j] && f[j - a[i]])f[j] = 1;}}}for (i = c1; i >= 0; --i) if (f[i]) break;if (sum - i <= c2) return 1;else return 0; } int main(){//freopen("din.txt","r",stdin);int i,j,T,cas = 1;scanf("%d",&T);while (T--){scanf("%d%d%d",&n,&c1,&c2);if (c1 > c2) swap(c1,c2);//c1始終是最小這樣在isok里面就優化了。for (i = 0; i < n; ++i) scanf("%d",&a[i]);int MSK = (1<<n);int len = 0;for (i = 1; i < MSK; ++i){if (isok(i)) msk[len++] = i;//記錄滿足要求的狀態 }for (i = 0; i < M; ++i) f[i] = inf;f[0] = 0;//01背包記錄最小搬運次數for (i = 0; i < len; ++i){for (j = MSK - 1; j >= msk[i]; --j){if (((j&msk[i]) == msk[i]) && f[j - msk[i]] != inf)f[j] = min(f[j],f[j - msk[i]] + 1);}}printf("Scenario #%d:\n",cas++);printf("%d\n\n",f[MSK - 1]);}return 0; }

pku 1837?Balance ?往背包里面放值

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

題意：

一個天枰，左右兩個臂膀的長度為15，有n個掛砝碼的位置，和m個重量不同的砝碼，砝碼的最大重量為25，問將所有砝碼都掛上得到平衡的可能數。

思路：

這想當于往背包里放值求最終值為0的種數。這里可以算出分別掛到兩邊的極限值為-7500 到7500 我們可以經他們映射到0-15000 ?然后往背包里面放值，看最后總出現0也即7500的個數。

更新中。。。

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

總結

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

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

背包

上一篇：《Effective C#》读书笔记——
下一篇：ＡＯ开发