题解：P1048 [NOIP 2005 普及组] 采药

· · 题解

题解区里的 dp 都是一模一样的，那我就来点不一样的吧。

大家都是从正面考虑前 n 个物品，时间为 m，所能得到的最大收益，但是这道题目还有另一种思路就是反过来：前 n 个物品，价值和为 m，需要的最小时间和。

我们还是从 dp 的要素入手：

  2. 当 n=m=0 的时候，我们什么都不取也就是最小重量是 0 其余的情况都初始化为极大值。
  3. 状态转移：我们什么都不干的话那么就是 f_{i,j}=f_{i-1,j}，如果我们要当前这个物品的话那么 f_{i,j}=\min\left\{f_{i,j},f_{i-1,j-v_i}+w_i\right\}。
  4. 最后我们的答案是从最大的价值开始遍历如果遍历到价值 i 时发现 f_{n,i}≤C 那么这个价值 i 就是我们要求的答案。

讲得这么详细了，直接上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int f[103][10003],w[103],v[103];
signed main(){
    //f[n][m]: 前 n 个物品，价值和为 m，需要的最小重量和
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    int C=read(),n=read();
    for(int i=1;i<=n;i++)w[i]=read(),v[i]=read();
    for(int i=1;i<=n;i++){
        //考虑第 i 个物品
        for(int j=100*i;j>=0;j--){
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=min(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    for(int i=100*n;i>=0;i--)if(f[n][i]<=C)printf("%d\n",i),exit(0);
    return 0;
}

亲测可过，请勿抄袭！