小结"/>
ACM心得 之 背包DP小结
（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦
目录
文章目录
- 目录
- 01背包
- POJ2184：两属性最大和值
- HDU2639-第k优解
- HDU3449:有依赖关系的背包
- HDU5188-带限制的01背包
- HDU3236-带限制的二维01背包GiftHunting
- Codeforces730J-01背包
- Codeforces864E-01背包记录路径
- 完全背包
- POJ3181-简单题-大数orJava
- POJ1787:完全背包记录路径 or
- poj2063 完全背包
- 硬币最少找零问题
- 多重背包
- hdu2844 多重背包模板题or二进制拆分
- POJ1787多重背包+记录路径
- POJ2392Space Elevator- 多重背包-
- ACM-ICPC 2018 焦作赛区网络预赛 K:Transport Ship
- 其他
- 结
01背包
POJ2184：两属性最大和值
#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define fuck(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e2 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
int n, sum;
int s[N][2], dp[200005];
int a[200005];//a[i]表示i体积的最大收益下你选择了多少个物品
int main(){while(~scanf("%d", &n)){int m = 0;for(int i=1;i<=n;++i){scanf("%d%d", &s[i][0],&s[i][1]);s[i][0]+=1000;m += s[i][0];}mme(dp, 0x80);mme(a, 0);dp[0] = 0;for(int i = 1; i <= n; ++i){for(int j = m; j >= s[i][0]; --j){if(dp[j]-a[j]*1000<dp[j-s[i][0]]+s[i][1]-(a[j-s[i][0]]+1)*1000){dp[j] = dp[j-s[i][0]]+s[i][1];a[j] = a[j-s[i][0]] + 1;}}}int mmax=0;for(int i=0;i<=m;++i){if(i-a[i]*1000<0||dp[i]<0)continue;mmax = max(mmax, dp[i]+i-a[i]*1000);}printf("%d\n", mmax);}return 0;
}
HDU2639-第k优解
#include<bits/stdc++.h>
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define fuck(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 1e2 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;int n, m, k;
int dp[1005][35];//dp[i][j]表示i体积下的第j优解的价值，dp[i][1]表示最大值
int s[1005][2];//0表价值，1表体积
int a[1005], b[1005];//合并前k优解，k个不一样的值
int main(){int tim;scanf("%d", &tim);while(tim--){scanf("%d%d%d", &n, &m, &k);for(int i=1;i<=n;++i){scanf("%d", &s[i][0]);}for(int i=1;i<=n;++i){scanf("%d", &s[i][1]);}mme(dp, 0);for(int i=1;i<=n;++i){for(int j=m;j>=s[i][1];--j){for(int t=1;t<=k;++t){a[t] = dp[j][t];b[t] = dp[j-s[i][1]][t]+s[i][0];}a[k+1] = b[k+1] = -1;int x=1,y=1,w=1;while(w<=k&&(x<=k||y<=k)){if(a[x]>=b[y]){dp[j][w]=a[x];++x;}else{dp[j][w]=b[y];++y;}if(w==1||dp[j][w]!=dp[j][w-1])++w;}}}printf("%d\n", dp[m][k]);}return 0;
}
HDU3449:有依赖关系的背包
(参考文献：背包九讲)
推荐博客：键盘里的青春 wuyiqi Thinker_0o0
对每个主件的附件里的物品跑一遍01背包，把主件加到跑完后的数组里，选择最优
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define fi first
#define se second
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define fuck(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 5e1 + 7;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
template<typename T>
inline T read(T&x){x=0;int f=0;char ch=getchar();while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x=f?-x:x;
}
typedef pair<int,int> pii;
int n, m;
vector<pii> mp[N];
int ar[N],len[N],dp[N][100005];
//dp[i][j]前i个购物车用j元钱能获得的最大价值
int main(){int tim, tc = 0;while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;++i)mp[i].clear();for(int i = 1;i <= n;++i){read(ar[i]),read(len[i]);for(int j = 0;j < len[i];++j){int a, b;read(a), read(b);//a是花费，b是所得mp[i].push_back(make_pair(a,b));//printf("%d %d\n", a,b);}}mme(dp, 0);for(int i=1;i<=n;++i){//第i组要买至少一个for(int j=0;j<ar[i];++j)dp[i][j] = -1;//有依赖关系，要赋值-1for(int j=ar[i];j<=m;++j){//减去入场卷，要买箱子里的东西先得买箱子dp[i][j] = dp[i-1][j-ar[i]];}for(int j=0;j<len[i];++j){for(int t=m;t>=mp[i][j].fi&&t>=ar[i];--t){if(dp[i][t-mp[i][j].fi]!=-1){ //注意依赖背包有不可能的情况dp[i][t]=max(dp[i][t-mp[i][j].fi]+mp[i][j].se,dp[i][t]);}}}//第i组不买for(int j=0;j<=m;++j)dp[i][j]=max(dp[i-1][j],dp[i][j]);}printf("%d\n", dp[n][m]);}return 0;
}
滚动数组优化
#include<bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define fi first
#define se second
#define lowbit(x) (x&(-(x)))
#define mme(a,b) memset((a),(b),sizeof((a)))
#define fuck(x) cout<<"* "<<x<<"\n"
#define iis std::ios::sync_with_stdio(false)
using namespace std;
typedef long long LL;
const int N = 5e1 + 7;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
int n, m;
int dp[100005], tmp[100005];
int main(){while(~scanf("%d%d",&n,&m)){mme(dp, 0);for(int i=1;i<=n;++i){int x,num;scanf("%d%d",&x,&num);for(int j=0;j<=m;++j)tmp[j]=dp[j];for(int j=0;j<num;++j){int w,v;scanf("%d%d",&w,&v);for(int t=m;t>=w;--t){tmp[t]=max(tmp[t], tmp[t-w]+v);}}for(int j=x;j<=m;++j){dp[j] = max(dp[j], tmp[j-x]);}}printf("%d\n", dp[m]);}return 0;
}
HDU5188-带限制的01背包
完成每个物品需要时间 t i ti ti，要求其不得再时刻 l i li li前完成，完成后可以得到 w i wi wi价值。
问最快多久能得到总价值 m ? m? m?
对于每件物品来说，最早能在 l i − t i ( 若 t i ≤ l i ) li-ti(若ti \leq li) li−ti(若ti≤li)时开始做。要求尽快完成又要遵守上述规则，我们将物品先按照 l i − t i li-ti li−ti从小到大排序，然后再进行 01 01 01背包。
#include<bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 1e3 + 7;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
int n, m;
struct lp{int t,l,v;
}cw[31];
int dp[100005];
bool cmp(lp &a, lp &b){return a.l-a.t<b.l-b.t;
}
int main(){while(~scanf("%d%d", &n,&m)){int tim = 0, tmp = 0;for(int i=1;i<=n;++i){scanf("%d%d%d", &cw[i].t,&cw[i].v,&cw[i].l);tim += cw[i].t; tmp = max(tmp, cw[i].l);}tim = max(tim,tmp);sort(cw+1,cw+1+n,cmp);mme(dp, 0);for(int i=1;i<=n;++i){for(int j=tim;j>=cw[i].t;--j){if(j>=cw[i].l){dp[j]=max(dp[j],dp[j-cw[i].t]+cw[i].v);}}}int ans=INF;for(int j=1;j<=tim;++j){if(dp[j]>=m){ans=j;break;}}if(ans!=INF)printf("%d\n", ans);else puts("zhx is naive!");}return 0;
}
HDU3236-带限制的二维01背包GiftHunting
题意虐狗的背包，大致就是你有两张卡，金额分别为 m 1 m1 m1和 m 2 m2 m2.有两类物品，一类是女票必须要的，一类是不必须的。
物品有两个属性：价格和欢乐值。不过你可以免费获得一个物品，问获取女票必须要的物品的前提下，女票的最高欢乐值是多少？若不能得到所有必须品则输出 − 1 -1 −1.
先对必需品 01 01 01背包判断能否全部购买，若不能输出 − 1 -1 −1，若能再对剩下的物品01背包得出最终答案。
状态表示：
d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1]容量为 i i i和 j j j使用能力的获得的最大欢乐值
d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0]容量为 i i i和 j j j不使用能力的获得的最大欢乐值
设必需品的欢乐值和为 s u m 1 sum1 sum1.
状态转移方程见代码。需要注意的是对于第二次背包有一个新条件，就是必须由欢乐值大于 s u m 1 sum1 sum1的状态转移来才行！
#include<bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 1e3 + 7;
const int INF = 0x3f3f3f3f;int n, m1, m2;
struct lp{int p,h;lp(){}lp(int a,int b){p=a,h=b;}
}cw[305],pp[305];
int dp[505][55][2];
//if Third dimension is 1 we use the free chance, vice versa
int main(){int tc=0;while(~scanf("%d%d%d",&m1,&m2,&n)){if(m1+m2+n==0)break;int n1 = 0,n2 = 0;for(int i=1,p,h,s;i<=n;++i){scanf("%d%d%d",&p,&h,&s);if(s)pp[n1++] = lp(p,h);else cw[n2++] = lp(p,h);}mme(dp, 0);int sum1=0;for(int i=0;i<n1;++i){sum1+=pp[i].h;for(int j=m1;j>=0;--j){for(int k=m2;k>=0;--k){dp[j][k][1]=max(dp[j][k][0]+pp[i].h,dp[j][k][1]);if(j-pp[i].p>=0)dp[j][k][1]=max(dp[j-pp[i].p][k][1]+pp[i].h,dp[j][k][1]);if(k-pp[i].p>=0)dp[j][k][1]=max(dp[j][k-pp[i].p][1]+pp[i].h,dp[j][k][1]);if(j-pp[i].p>=0)dp[j][k][0]=max(dp[j-pp[i].p][k][0]+pp[i].h,dp[j][k][0]);if(k-pp[i].p>=0)dp[j][k][0]=max(dp[j][k-pp[i].p][0]+pp[i].h,dp[j][k][0]);}}}int flag=0;for(int j=0;j<2;++j){if(dp[m1][m2][j]==sum1)flag=1;}printf("Case %d: ", ++tc);if(!flag){printf("-1\n\n");continue;}for(int i=0;i<n2;++i){for(int j=m1;j>=0;--j){for(int k=m2;k>=0;--k){if(dp[j][k][0]>=sum1)dp[j][k][1]=max(dp[j][k][0]+cw[i].h,dp[j][k][1]);if(j-cw[i].p>=0&&dp[j-cw[i].p][k][1]>=sum1)dp[j][k][1]=max(dp[j-cw[i].p][k][1]+cw[i].h,dp[j][k][1]);if(k-cw[i].p>=0&&dp[j][k-cw[i].p][1]>=sum1)dp[j][k][1]=max(dp[j][k-cw[i].p][1]+cw[i].h,dp[j][k][1]);if(j-cw[i].p>=0&&dp[j-cw[i].p][k][0]>=sum1)dp[j][k][0]=max(dp[j-cw[i].p][k][0]+cw[i].h,dp[j][k][0]);if(k-cw[i].p>=0&&dp[j][k-cw[i].p][0]>=sum1)dp[j][k][0]=max(dp[j][k-cw[i].p][0]+cw[i].h,dp[j][k][0]);}}}for(int j=0;j<2;++j){sum1=max(sum1,dp[m1][m2][j]);}printf("%d\n\n", sum1);}return 0;
}
Codeforces730J-01背包
给你n个装有c升水容量为v升的瓶子，问他们装到最少几个瓶子里？在瓶子数最少的前提下，问最少转移多少升水？
最少多少个瓶子就是排个序选最大的k个就好了，对于最少需要转移多少升水不就是问k个瓶子已经装的最多水量吗？
d p [ i ] [ j ] dp[i][j] dp[i][j]表示选取i个瓶子，总容量为j现有的最多含水量。
d p [ i ] [ j ] = m a x ( d p [ i ] [ j − v ] + c ) dp[i][j]=max(dp[i][j-v]+c) dp[i][j]=max(dp[i][j−v]+c)
#include<bits/stdc++.h>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = 1e3 + 7;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;void read(int &sum){sum=0;char ch=getchar();while(!(ch>='0'&&ch<='9'))ch=getchar();while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
}
int n, m;
struct lp{int c,v;
}cw[N];
//类01背包
int dp[105][10005];
bool cmp(lp &a,lp &b){return a.v>b.v;
}
int main(){while(~scanf("%d", &n)){int sum=0,sum1=0;for(int i=0;i<n;++i){read(cw[i].c);sum+=cw[i].c;}for(int i=0;i<n;++i){read(cw[i].v);sum1+=cw[i].v;}sort(cw,cw+n,cmp);int k=0,tm=0;for(int i=0;i<n&&tm<sum;++i,++k){tm+=cw[i].v;}mme(dp, -1);dp[0][0]=0;tm = 0;for(int i=0;i<n;++i){tm+=cw[i].v;for(int j=k;j>=1;--j){//类01背包for(int h=tm;h>=0;--h){if(h>=cw[i].v&&dp[j-1][h-cw[i].v]>=0){dp[j][h]=max(dp[j-1][h-cw[i].v]+cw[i].c, dp[j][h]);}}}}int ans=0;for(int i=sum;i<=sum1;++i){ans=max(ans,dp[k][i]);}printf("%d %d\n", k, sum-ans);}return 0;
}
Codeforces864E-01背包记录路径
一种记忆化搜索，一种vector暴力。数据范围比较小，暴力贼快！
ac_code:记忆化搜索
#include<cstdio>
#include<cstring>
#include <vector>
#include<algorithm>
#define pb push_back
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = (int)2e5+7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const int MOD = 1000000007;
int n;
int val[105], tim[105], dl[105];
int dp[N];
int is[105][2005];
int tot,stak[1005];
struct lp{int v, t, d, id;
}cw[105];
bool cmpd(lp &a, lp &b){if(a.d != b.d)return a.d < b.d;return a.t < b.t;
}
void fidn(int n,int m){if(n==0)return;if(is[n][m]){stak[tot++] = cw[n].id;fidn(n-1,m-tim[n]);}else{fidn(n-1,m);}
}
int main(){while(~scanf("%d", &n)){int m = 0;for(int i = 1; i <= n; ++i){scanf("%d%d%d", &tim[i], &dl[i], &val[i]);m = max(m, dl[i]);cw[i].t = tim[i];cw[i].d = dl[i];cw[i].v = val[i];cw[i].id = i;}sort(cw + 1, cw + n + 1,cmpd);for(int i = 1; i <= n; ++i){tim[i] = cw[i].t;dl[i] = cw[i].d;val[i] = cw[i].v; }mme(is, 0);memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i){for(int j = dl[i] - 1; j >= tim[i]; --j){if(dp[j] < dp[j-tim[i]] + val[i]){dp[j] = dp[j-tim[i]] + val[i];is[i][j] = 1;}}}int tmax = dp[m], p = m;for(int i = 1; i <= m; ++i){if(dp[i] > tmax){tmax = dp[i];p = i;}}m = p;tot = 0;fidn(n, m);printf("%d\n", dp[m]);printf("%d\n", tot);for(int i = tot-1; i >= 0; --i){printf("%d%c", stak[i], " \n"[i==0]);}}return 0;
}
ac_code:暴力记录
#include<cstdio>
#include<cstring>
#include <vector>
#include<algorithm>
#define lowbit(x) (x)&(-(x))
#define lson rt<<1
#define rson rt<<1|1
#define pb push_back
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = (int)2e5+7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const uLL base = 1572872831;
const int MOD = 1000000007;
int n;
int val[105], tim[105], dl[105];
int dp[N];
vector<int> num[N];
struct lp{int v, t, d, id;
}cw[105];
bool cmpd(lp &a, lp &b){if(a.d != b.d)return a.d < b.d;return a.t < b.t;
}
int main(int argc, char const *argv[]){while(~scanf("%d", &n)){int m = 0;for(int i = 0; i <= n; ++i){num[i].clear();}for(int i = 1; i <= n; ++i){scanf("%d%d%d", &tim[i], &dl[i], &val[i]);m = max(m, dl[i]);cw[i].t = tim[i];cw[i].d = dl[i];cw[i].v = val[i];cw[i].id = i;}sort(cw + 1, cw + n + 1,cmpd);for(int i = 1; i <= n; ++i){tim[i] = cw[i].t;dl[i] = cw[i].d;val[i] = cw[i].v; }memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i){for(int j = dl[i] - 1; j >= tim[i]; --j){if(dp[j] < dp[j-tim[i]] + val[i]){dp[j] = dp[j-tim[i]] + val[i];num[j] = num[j-tim[i]];num[j].pb(i);}}}int tmax = dp[m], p = m;for(int i = 1; i <= m; ++i){if(dp[i] > tmax){tmax = dp[i];p = i;}}m = p;printf("%d\n%d\n", dp[m], num[m].size());if(num[m].size()){printf("%d", cw[num[m][0]].id);;num[m].erase(num[m].begin());if(num[m].size()){for(auto x: num[m]){printf(" %d", cw[x].id);}}printf("\n");}}return 0;
}完全背包
POJ3181-简单题-大数orJava
很裸的题，就是问给你1-k的硬币问组成n元钱有多少种组成方法。
import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.io.PrintStream;
import java.util.Scanner;public class Main{static PrintStream putOut = System.out;static BigInteger dp[] = new BigInteger[1005];public static void main(String[] args) {Scanner cin = new Scanner(System.in);while(cin.hasNext()){int n = cin.nextInt(), k = cin.nextInt();dp[0] = BigInteger.valueOf(1);for(int i = 1; i <= n; ++i)dp[i]=BigInteger.valueOf(0);for(int i = 1; i <= k; ++i){for(int j = i; j <= n; ++j){dp[j] = dp[j].add(dp[j - i]);}}putOut.println(dp[n]);}}
}
POJ1787:完全背包记录路径 or
听说可以完全背包，多重背包，母函数写。这里放一个完全背包的写法。
这题就是给你4种硬币的数量，问可以最多用多少个硬币要组成n元钱。
要最多的话，要把硬币面值从小到大枚举，并且记录每种硬币使用的次数。判断条件是如果能更多就更新。
如果求最少是不是可以反着枚举呢？
#include<cstdio>
#include<cstring>
#include <vector>
#include <cmath>
#include<algorithm>
#include <cmath>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = (int)1e4 + 7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
int dp[10010];
int n;
int w[4]={1,5,10,25}, num[4], have[10010];
//dp[i]表示组成i元钱最多用的硬币数量
int path[10010], ans[30], tot;
int main(){while(~scanf("%d", &n)){int m = n;for(int i = 0; i < 4; ++i)scanf("%d", &num[i]), m += num[i];if(m == 0)break;mme(dp, 0);mme(path, 0);dp[0] = 1;for(int i = 0; i < 4; ++i){mme(have, 0);//统计第i个硬币使用数量，不需要开4维数组，每次清空一下即可for(int j = w[i]; j <= n; ++j){if(dp[j - w[i]]&&dp[j - w[i]] + 1 > dp[j]&&have[j - w[i]]<num[i]){dp[j] = dp[j - w[i]] + 1;have[j] = have[j - w[i]] + 1;path[j] = j - w[i];}}}if(dp[n] == 0){printf("Charlie cannot buy coffee.\n");continue;}tot = 0;mme(ans, 0);while(n){ans[n - path[n]]++;//printf("%d %d\n", n, path[n]);n = path[n];}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[1],ans[5],ans[10],ans[25]);}return 0;
}
poj2063 完全背包
看起来难，其实很裸。
你有起始资金 m m m元，可以投资 t t t年。有 n n n种债卷，买入需要 w i wi wi元，每年可以获利 v i vi vi元。保证 m m m和 w i wi wi是 1000 1000 1000的倍数。然后题目说了每年赚的钱的可以作为本金。
冷静分析，应该是每年都要做一次完全背包。然后把 m m m和 w i wi wi都除 1000 1000 1000来节约空间减少时间。
然后做裸的完全背包就可以了，看代码会懂的。
#include<cstdio>
#include<cstring>
#include <vector>
#include <cmath>
#include<algorithm>
#include <cmath>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = (int)1e4 + 7;
const int MX = 1000+7;
const int MAXM = 3e5+7;
const int INF = 0x3f3f3f3f;
int n, t, m;
int w[20], v[20];
int dp[100010];
int main(){int tim;scanf("%d", &tim);while(tim--){scanf("%d%d", &m, &t);scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d%d", &w[i], &v[i]);w[i] /= 1000;}int sum = m;for(int time = 0; time < t; ++time){mme(dp, 0);m = sum / 1000;for(int i = 0; i < n; ++i){for(int j = w[i]; j <= m; ++j){dp[j] = max(dp[j], dp[j-w[i]]+v[i]);}}sum += dp[m];}printf("%d\n", sum);}return 0;
}
硬币最少找零问题
多重背包
01背包是每种物品只能使用一次，完全背包是无穷次，而多重背包则是有限次。解法有二进制优化+01背包，当然也有通用解法，此解法把01背包和多重背包组合起来解决这三种背包问题。
hdu2844 多重背包模板题or二进制拆分
抽象点理解就是： n n n种硬币， m m m为金额上限值。每个硬币有面值 v i vi vi和数量 t i ti ti，问用这些硬币能组成多少种金钱。
二进制优化+01背包
#include<cstdio>
#include<cstring>
#include <vector>
#include <cmath>
#include<algorithm>
#include <cmath>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int N = (int)1e4 + 7;
int n, m;
int dp[100007], s[10005];
int val[105];
int main(){while(~scanf("%d%d", &n, &m)&&(n+m)){int tot = 0;for(int i = 1; i <= n; ++i)scanf("%d", &val[i]);for(int i = 1, u; i <= n; ++i){scanf("%d", &u);for(int j = 1; j <= u; j <<= 1){s[tot++] = j * val[i];u -= j;}if(u)s[tot++] = u * val[i];}mme(dp, 0);dp[0] = 1;for(int i = 0; i < tot; ++i){for(int j = m; j >= s[i]; --j){dp[j] = max(dp[j], dp[j-s[i]]);}}tot = 0;for(int i = m; i >= 1; --i){tot += dp[i];}printf("%d\n", tot);}return 0;
}
多重背包模板
#include<cstdio>
#include<cstring>
#include <vector>
#include <cmath>
#include<algorithm>
#include <cmath>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N = (int)1e4 + 7;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
int n, m;
int dp[100007], val[10005], num[10005];
void compack(int cost,int happy){for(int i = cost; i <= m; ++i){dp[i] = max(dp[i], dp[i-cost]+happy);}
}
void zopack(int cost,int happy){for(int i = m; i >= cost; --i){dp[i] = max(dp[i], dp[i-cost]+happy);}
}
void mulpack(int cost,int happy,int amount){if(amount*cost >= m)compack(cost, happy);else{for(int i = 1; i <= amount; i <<= 1){zopack(cost*i, happy*i);amount -= i;}if(amount){zopack(cost*amount, happy*amount);}}
}
int main(){while(~scanf("%d%d", &n, &m)&&(n+m)){int tot = 0;for(int i = 1; i <= n; ++i)scanf("%d", &val[i]);for(int i = 1, u; i <= n; ++i)scanf("%d", &num[i]);mme(dp, 0x80);dp[0] = 0;for(int i = 1; i <= n; ++i){mulpack(val[i], val[i], num[i]);}tot = 0;for(int i = m; i >= 1; --i){tot += (dp[i]==i);}printf("%d\n", tot);}return 0;
}
POJ1787多重背包+记录路径
题意在完全背包哪里已经说了。
d p [ i ] dp[i] dp[i] 表示的是 i i i元钱用的最多硬币数量
d p [ i ] = d p [ i − c o s t ] + n u m dp[i] = dp[i-cost] + num dp[i]=dp[i−cost]+num && ( d p [ i − c o s t ] 合 法 ) (dp[i-cost] 合法) (dp[i−cost]合法)
//两种记录路径的方法，下面的注释是一种
#include<bits/stdc++.h>
#define lowbit(x) (x)&(-(x))
#define all(x) x.begin(),x.end()
#define mme(a,b) memset((a),(b),sizeof((a)))
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const LL N = 1e7+7;
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const int MX = 1e6 + 7;
int dp[10010];
int n;
int w[4]={1,5,10,25}, num[4];
int sum[10010][4];
LL path[10010];
int tot, ans[30];void compack(int cost,int id){for(int i = cost; i <= n; ++i){if(dp[i-cost]+1 > dp[i]&&dp[i-cost] >= 0){dp[i] = dp[i-cost]+1;/*for(int j = 0; j <4; ++j)sum[i][j]=sum[i-cost][j];sum[i][id]++;*/path[i] = id*N + i - cost;}}
}
void zopack(int cost,int Num,int id){for(int i = n; i >= cost; --i){if(dp[i-cost]+Num > dp[i]&&dp[i-cost] >= 0){dp[i] = dp[i-cost]+Num;/*for(int j = 0; j <4; ++j)sum[i][j]=sum[i-cost][j];sum[i][id]+=Num;*/path[i] = id*N + i - cost;}}
}
void mulpack(int cost,int amount,int id){if(amount*cost >= n)compack(cost, id);else{for(int i = 1; i <= amount; i <<= 1){zopack(cost*i, i, id);amount -= i;}if(amount){zopack(cost*amount, amount, id);}}
}
int main(){while(~scanf("%d", &n)){int m = n;for(int i = 0; i < 4; ++i)scanf("%d", &num[i]), m += num[i];if(m == 0)break;mme(sum ,0);mme(path, 0);mme(dp, 0x80);dp[0] = 0;for(int i = 0; i < 4; ++i){mulpack(w[i], num[i], i);}if(dp[n] <= 0){printf("Charlie cannot buy coffee.\n");continue;}tot = 0;mme(ans, 0);while(n){LL id = path[n]/N;int s = path[n]%N;ans[w[id]] += (n - s)/w[id];n = s;}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[1],ans[5],ans[10],ans[25]);}return 0;
}POJ2392Space Elevator- 多重背包-
良心样例。敲完好发现怎么都过不了样例，代码又没什么问题，仔细一想，好像得排个序，只能说良心样例。
我理解的题意：n种柱子，第i个柱子有ci个，长度为hi，最高不能超过ai，问这些柱子能组成的最高高度。
比一般的多重背包多了个条件，不过也挺好处理的，就是不同物品修改一下上限就好咯。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mme(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;int dp[120010];
int n, m;
int h[405], a[405], c[405];
struct lp{int h,a,c;
}cw[405];
bool cmp(lp &A, lp &B){if(A.a!=B.a)return A.a<B.a;return A.h<B.h;
}
void zopack(int cost,int m){for(int i = m; i >= cost; --i){if(dp[i-cost] + cost > dp[i]){dp[i] = dp[i-cost] + cost;}}
}
void compack(int cost,int m){for(int i = cost; i <= m; ++i){if(dp[i-cost] + cost > dp[i]){dp[i] = dp[i-cost] + cost;}}
}
void mulpack(int cost,int height,int amount){if(amount*cost >= INF)compack(cost,height);//把INF改成height就是普通模板，写INF就是二进制拆分else{for(int i = 1; i <= amount; i <<= 1){zopack(cost*i,height);amount -= i;}if(amount){zopack(cost*amount,height);}}
}
int main(){int tc = 0;while(~scanf("%d", &n)){int sum = 0;for(int i = 1; i <= n; ++i){scanf("%d%d%d", &h[i], &a[i], &c[i]);sum = max(sum, a[i]);cw[i].h=h[i];cw[i].a=a[i];cw[i].c=c[i];}sort(cw+1,cw+1+n,cmp);for(int i = 1; i <= n; ++i){h[i]=cw[i].h;a[i]=cw[i].a;c[i]=cw[i].c;}mme(dp, 0x80);dp[0] = 0;for(int i = 1; i <= n; ++i){mulpack(h[i], a[i], c[i]);}/*for(int i = 1; i <= sum; ++i){printf("%d ", dp[i]);}printf("\n");*/int ans = 0;for(int i = sum; i >= 1; --i){if(dp[i] == i){ans = i;break;}}printf("%d\n", ans);}return 0;
}
ACM-ICPC 2018 焦作赛区网络预赛 K:Transport Ship
#include <bits/stdc++/h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;int v[55], c[55];
LL dp[10000+5];
int n, q;
int main() {int T;cin >> T;while (T--) {memset(dp,0,sizeof(dp));scanf("%d%d",&n,&q);for(int i = 1;i<=n;i++){scanf("%d%d",&v[i],&c[i]);}dp[0] = 1;for(int i = 1;i<=n;i++){for(int k = 0;k<c[i];k++){for(int j = 10000;j>=0;j--){if((j-(1<<k)*v[i])>=0)dp[j] = (dp[j]+dp[j-(1<<k)*v[i]])%mod;}}}while(q--){int x;scanf("%d",&x);printf("%lld\n",dp[x]%mod);}}return 0;
}
其他
emmm
结
？
背包问题都是些很基础的问题，最开始学的dp就是背包问题，不难理解，但是变形非常多，一定要吃透，因为不可能会花很多时间再去练习，可能有时间再来回顾一遍背包九讲，不管怎样，背包问题要非常熟悉才行。
更多推荐
ACM心得 之 背包DP小结
发布评论