混合背包 hdu5410 CRB and His Birthday
2024-09-05 04:22:07
传送门:点击打开链接
题意:你有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;
}
最新文章
- linux防火墙开启端口
- layer弹出层 layer源码
- (iOS)项目总结-项目中遇到的各种的问题和解决方法
- Java之工厂方法
- 深入理解HTML表格
- RabbitMq基本使用
- svn 检出 Check out 请求的名称有效,但是找不到请求的类型的数据。
- POJ2282:The Counting Problem(数位DP)
- createThread和_beginthreadex区别
- gcc编译器用法
- SQL之case when then用法(用于分类统计)
- 洛谷P1434滑雪题解及记忆化搜索的基本步骤
- Mysql常用单词
- VC++ 学习笔记3 获取编辑框字符串
- Intel RDT
- Leetcode 647. Palindromic Substrings
- CenOS6.5下源码安装vim-7.4
- Windows 下的高 DPI 应用开发(UWP / WPF / Windows Forms / Win32)
- MySQL常见错误代码说明
- java实现验证码功能主要代码