首页 > 代码库 > 混合背包 hdu5410 CRB and His Birthday
混合背包 hdu5410 CRB and His Birthday
传送门:点击打开链接
题意:你有M块钱,如今有N件商品
第i件商品要Wi块,假设你购买x个这种商品。你将得到Ai*x+Bi个糖果
问能得到的最多的糖果数
思路:很好的一道01背包和全然背包结合的题目
首先,对于第i件商品,假设仅仅买1个,得到的价值是Ai+Bi
假设在买1个的基础上再买。得到的价值就是Ai
也就是说,除了第一次是Ai+Bi。以后购买都是Ai
那么,我们是否能将i商品拆分成两种商品,当中两种商品的代价都是Wi,
第一种的价值是Ai+Bi,可是仅仅同意买一次
另外一种的价值是Ai。能够无限次购买
接下来我们来讨论这样拆的正确性
理论上来讲,买另外一种之前。必需要买第一种
可是对于这道题,由于Ai+Bi>=Ai是必定的,由于Bi肯定是非负
所以对于代价同样。价值大的肯定会被先考虑
换句话来说,假设已经開始考虑另外一种商品了。那么第一种商品就肯定已经被加入到背包里了~
所以。这题我们把n件商品拆分成2*n件商品。对于第一种商品做01背包,对于另外一种商品做全然背包,这样就把题目转换成了很熟悉的题目。也就能顺利AC了
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<string> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #define FIN freopen("input.txt","r",stdin) using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MX = 2e4 + 5; int dp[MX]; int A[MX], B[MX], rear; int main() { int T, V, n; //FIN; scanf("%d", &T); while(T--) { memset(dp, 0, sizeof(dp)); scanf("%d%d", &V, &n); for(int i = 1; i <= n; i++) { int w, a, b; scanf("%d%d%d", &w, &a, &b); A[i] = w; B[i] = a + b; A[i + n] = w; B[i + n] = a; } for(int i = 1; i <= n; i++) { for(int j = V; j >= A[i]; j--) { dp[j] = max(dp[j], dp[j - A[i]] + B[i]); } } for(int i = 1 + n; i <= 2 * n; i++) { for(int j = A[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - A[i]] + B[i]); } } printf("%d\n", dp[V]); } return 0; }
混合背包 hdu5410 CRB and His Birthday
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。