珠海建网站,网页设计公司业绩介绍,17zwd一起做网站普宁,青岛网站建设团队疯狂的采药
题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大的医师。为此#xff0c;他想拜附近最有威望的医师为师。医师为了判断他的资质#xff0c;给他出了一个难题。医师把他带到一个到处都是草…疯狂的采药
题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同种类的草药采每一种都需要一些时间每一种也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang你能完成这个任务吗
此题和原题的不同点 1 1 1. 每种草药可以无限制地疯狂采摘。 2 2 2. 药的种类眼花缭乱采药时间好长好长啊师傅等得菊花都谢了
输入格式
输入第一行有两个整数分别代表总共能够用来采药的时间 t t t 和代表山洞里的草药的数目 m m m。
第 2 2 2 到第 ( m 1 ) (m 1) (m1) 行每行两个整数第 ( i 1 ) (i 1) (i1) 行的整数 a i , b i a_i, b_i ai,bi 分别表示采摘第 i i i 种草药的时间和该草药的价值。
输出格式
输出一行这一行只包含一个整数表示在规定的时间内可以采到的草药的最大总价值。
样例 #1
样例输入 #1
70 3
71 100
69 1
1 2样例输出 #1
140提示
数据规模与约定
对于 30 % 30\% 30% 的数据保证 m ≤ 1 0 3 m \le 10^3 m≤103 。对于 100 % 100\% 100% 的数据保证 1 ≤ m ≤ 1 0 4 1 \leq m \le 10^4 1≤m≤104 1 ≤ t ≤ 1 0 7 1 \leq t \leq 10^7 1≤t≤107且 1 ≤ m × t ≤ 1 0 7 1 \leq m \times t \leq 10^7 1≤m×t≤107 1 ≤ a i , b i ≤ 1 0 4 1 \leq a_i, b_i \leq 10^4 1≤ai,bi≤104。 思路
在这个问题中有一个背包其容量是时间t还有m种不同的草药每种草药都有自己的采集时间a[i]和价值b[i]。目标是在不超过背包容量的情况下最大化背包中草药的总价值。
可以将每种草药视为一种物品其“重量”是采集时间其“价值”是草药的价值。这个问题的特点是每种草药可以无限次采集只要时间允许。这就是所谓的“完全背包”问题。
定义状态dp[j]为当背包容量为j时能够获得的最大价值。初始化状态时假设背包为空所以所有的dp[j]都为0。
然后开始填充状态表。对于每种草药i都会尝试将其添加到背包中看看是否能提高背包的总价值。具体来说对于每个可能的背包容量j如果可以将草药i添加到背包中即j a[i]那么就有两种选择一是不添加草药i此时背包的总价值仍然是dp[j]二是添加草药i此时背包的总价值变为dp[j - a[i]] b[i]。目标是使背包的总价值最大所以选择两者中的较大值作为新的dp[j]。
这是完全背包问题而不是01背包问题。在完全背包问题中每种物品可以被选择多次因此在考虑是否选择当前物品时需要查看在选择该物品多次的情况下能够获得的最大价值。
在这个问题中for (int j a[i]; j t; j) 的作用是遍历所有可能选择当前物品的情况。由于可以选择当前物品多次因此需要从小到大遍历 j。这样当考虑到 j 时dp[j - a[i]] 对应的是已经选择了当前物品的情况因此 dp[j] 可以通过选择当前物品来更新。
如果从大到小遍历 j即 for (int j t; j a[i] j--)那么当考虑到 j 时dp[j - a[i]] 对应的是还没有选择当前物品的情况因此 dp[j] 只能通过不选择当前物品来更新。这就变成了01背包问题每种物品只能被选择一次。
最后输出dp[t]这就是当背包容量为t时能够获得的最大价值也就是答案。 AC代码
#include algorithm
#include iostream
#define AUTHOR HEX9CF
#define ll long long
using namespace std;const int N 1e7 7;int t, m;
// 时间价值
int a[N], b[N];
ll dp[N];int main() {cin t m;for (int i 1; i m; i) {cin a[i] b[i];}for (int i 1; i m; i) {for (int j a[i]; j t; j) {dp[j] max(dp[j], dp[j - a[i]] b[i]);}}cout dp[t] endl;return 0;
}
