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

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

大家都是从正面考虑前

n

个物品，时间为

m

，所能得到的最大收益，但是这道题目还有另一种思路就是反过来：前

n

个物品，价值和为

m

，需要的最小时间和。

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

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

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

CPP

#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;
}

亲测可过，请勿抄袭！

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

文章操作

相关推荐

评论

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