【题目来源】https://www.luogu.com.cn/problem/P1616【题目描述】LiYuxiang 是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同种类的草药采每一种都需要一些时间每一种也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”如果你是 LiYuxiang你能完成这个任务吗?此题和原题的不同点1.每种草药可以无限制地疯狂采摘。2.药的种类眼花缭乱采药时间好长好长啊师傅等得菊花都谢了【输入格式】输入第一行有两个整数分别代表总共能够用来采药的时间t和代表山洞里的草药的数目 m。第 2 到第m1行每行两个整数第i1行的整数 aibi 分别表示采摘第 i 种草药的时间和该草药的价值。【输出格式】输出一行这一行只包含一个整数表示在规定的时间内可以采到的草药的最大总价值。【输入样例】70 371 10069 11 2【输出样例】140【数据范围】● 对于 30% 的数据保证 m≤10^3。● 对于 100% 的数据保证1≤m≤10^41≤t≤10^7且1≤m×t≤1071≤ai,bi≤10^4。【算法分析】● 本题数据需要开到long long。● 完全背包问题状态转移方程的推导过程设 f[i][j] 为将前 i 种物品装入容量为 j 的背包中所获得的最大价值vol[i] 为第 i 中物品的体积val[i] 为第 i 种物品的价值。Letj j - vol[i], and taking into account thatk * vol[i] j, then we have:After organizing and simplifying, we obtain:Addval[i]to both sides, we get:Now, lets compare Equations (1) and (3) together and draw a conclusion.From this, the state transition equation for the one-dimensional optimized Complete knapsack problem can be obtained.● 本文公式的 LaTex 代码1Equation 1 的 LaTex 代码f[i][j]\max\left\{ \begin{matrix} f[i-1][j] \\ f[i-1][j-\text{vol}[i]]\text{val}[i] \\ f[i-1][j-2\text{vol}[i]]2\text{val}[i] \\ \cdots \\ f[i-1][j-k\text{vol}[i]]k\text{val}[i] \end{matrix} \right\} (Equation 1)2Equation 2 的 LaTex 代码f[i][j-\text{vol}[i]]\max\left\{ \begin{matrix} f[i-1][j-\text{vol}[i]] \\ f[i-1][j-2\text{vol}[i]]\text{val}[i] \\ f[i-1][j-3\text{vol}[i]]2\text{val}[i] \\ \cdots \\ f[i-1][j-k\text{vol}[i]](k-1)\text{val}[i] \end{matrix} \right\} (Equation 2)3Equation 3 的 LaTex 代码f[i][j-\text{vol}[i]]\text{val}[i]\max\left\{ \begin{matrix} f[i-1][j-\text{vol}[i]]\text{val}[i] \\ f[i-1][j-2\text{vol}[i]]2\text{val}[i] \\ f[i-1][j-3\text{vol}[i]]3\text{val}[i] \\ \cdots \\ f[i-1][j-k\text{vol}[i]]k\text{val}[i] \end{matrix} \right\} (Equation 3)4Equation 4 的 LaTex 代码f[i][j]\max\bigl\{f[i-1][j],\ f[i][j-\text{vol}[i]]\text{val}[i]\bigr\} (Equation 4)【算法代码】#includebits/stdc.h using namespace std; typedef long long LL; const int maxn1e75; LL f[maxn]; int main() { int n,V; cinVn; for(int i1; in; i) { int vol,val; cinvolval; for(int jvol; jV; j) f[j]max(f[j],f[j-vol]val); } coutf[V]endl; return 0; } /* in: 70 3 71 100 69 1 1 2 out: 140 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/125939103https://blog.csdn.net/hnjzsyjyj/article/details/109633115https://blog.csdn.net/hnjzsyjyj/article/details/126132364