高级光能
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 22 个整数 TT（1 \le T \le 10001≤T≤1000）和 MM（1 \le M \le 1001≤M≤100），用一个空格隔开，TT 代表总共能够用来采药的时间，MM 代表山洞里的草药的数目。
接下来的 MM 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1复制
70 3 71 100 69 1 1 2
输出 #1复制
3
说明/提示
- 对于 30\%30% 的数据，M \le 10M≤10；
- 对于全部的数据，M \le 100M≤100。
NOIP2005 普及组 第三题
刘欣然在2020-07-13 17:09:29追加了内容
- 不要题解
中级天翼
01背包模版题，没学过不要做
初级光能
DP:
int main()
{
数入
for(int i=1;i<=n;i++)
数入
for(int l=1;l<=n;l++)
for(int y=t;y>0;y--)
{
if(a[l][1]<=y)
{
f[l][y]=max(f[l-1][y],f[l-1][y-a[l][1]]+a[l][2]);
}
else f[l][y]=f[l-1][y];
}
输出f[n][t]
}
王泽宇在2020-07-13 18:37:57追加了内容
搜索：
void lj(int x)
{
for(int i=1;i<=m;i++)
{
if(c[i][3]&&c[i][1]<=x)
{
y+=c[i][2];
x-=c[i][1];
c[i][3]=0;
lj(x);
if(max<y) max=y;
c[i][3]=1;
y-=c[i][2];
x+=c[i][1];
}
}
}
int main()
{
数入
for(int l=1;l<=m;l++)
{
数入c[l][1]//时间
数入c[l][2]//价值
c[l][3]=1;
}
lj(t);
输出max
}
王泽宇在2020-07-13 18:38:16追加了内容
借鉴别人的
初级启示者
首先，这题是一道水的不能在水的题了
其次，我还是想说这题真的太水了，就是一模一样的01背包问题，输入输出都没改
就是改了一个题目背景
转化时间为背包容量和草药占的量
先讲一下二维 dpdp：
让我假设现在的背包的容量是 C=10C=10；
物品编号：1\ \ \ 2\ \ \ 31 2 3
物品重量：5\ \ \ 6\ \ \ 45 6 4
物品价值：20\ 10\ 1220 10 12
用v[i]表示物品价值，w[i]表示物品重量，要使得放入背包的物品价值最大化，我们知道用贪心是不行的！
所以接下来开始动规：
首先定义状态 dp[i][j]dp[i][j] 以 jj 为容量为放入前i个物品(按 ii 从小到大的顺序)的最大价值，那么 i=1i=1 的时候，放入的是物品 11 ，这时候肯定是最优的啦！
那考虑一下 jj，jj 是当前容量，如果 j<5j<5，那么是不是就不能放，dp[1][j](j<5)=0dp[1][j](j<5)=0；那如果 j>5j>5，就可以放了，dp[1][j](j>=5)=20dp[1][j](j>=5)=20；
接着 i=2i=2 放两个物品，求的就是 dp[2][j]dp[2][j] 了，当 j<5j<5 的时候，是不是同样的 dp[2][j](j<5)dp[2][j](j<5) 等于00；那当 j<6j<6 是不是还是放不下第二个，只能放第一个；
那 j>6j>6 呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现 dp[2][j](j>6)=20dp[2][j](j>6)=20，这个 2020 怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品；
让我们假设一下 j=10j=10 吧，可能会比较好理解！这时候： dp[2][10] = max((dp[1][10-w[2]])+v[2],dp[1][10])dp[2][10]=max((dp[1][10−w[2]])+v[2],dp[1][10])
dp[2][10] = max(dp[1][4])+10,dp[1][10])dp[2][10]=max(dp[1][4])+10,dp[1][10])
是不是很明显了呢，dp[1][4]+10dp[1][4]+10 是选择了第二个，于是容量相应就减少成 44，之前已经得出 dp[1][4]=0dp[1][4]=0，就是说选了物品 22，物品 11 就选不了了；dp[1][10]dp[1][10] 是不选择第二个，只选择第一个 dp[1][10]dp[1][10] 是等于 2020 的，于是得出 dp[2][10]=20dp[2][10]=20
到这里就可以了，依次类推，动态转移方程为：dp[i][j] = max(dp[i-1][j-w[i]])+v[i],dp[i-1][j])dp[i][j]=max(dp[i−1][j−w[i]])+v[i],dp[i−1][j])
但是好像还有一些问题没考虑完.........
看回例子：
物品编号：1\ \ \ 2\ \ \ 31 2 3
物品重量：5\ \ \ 6\ \ \ 45 6 4
物品价值：20\ 10\ 1220 10 12
我们知道 dp[1][j](j<5)=20dp[1][j](j<5)=20，dp[2][j](j=5)dp[2][j](j=5) 的时候是多少呢？我们看到动态转移方程并没有考虑 j<w[i]j<w[i] 的情况，但是我们可以加进去，由于 dp[2][5]dp[2][5] 我们看出来是等于 55 的，为什么？因为不能选第二个，只能选第一个，所以..... dp[2][5]dp[2][5] 是不是刚好等于 dp[1][5]dp[1][5] 了呢！所以当 j<w[i]j<w[i] 的时候，dp[i][j] = dp[i-1][j]dp[i][j]=dp[i−1][j] 就好了，是不是很神奇呢！
//注：出处不是我，是deco主播的
