---

思路

首先，这是一道背包问题，其实就是动态规划。

我们用fi,jfi,j表示可以采前面ii种药，用jj个时间单位能够采到药的最大价值。

一道01背包问题,01背包，就是一种物品只能有取和不取两种，当我们来到fi,jfi,j时，可以采一次第ii药也就是fi,j−tifi,j−ti，就是要留出titi来采这个药(肯定要使j≥tij≥ti才可以采)，当然也可以不采，那么就是fi−1,jfi−1,j就是这个第ii种药不采，采前面i−1i−1中药的最大价值。

所以转移公式就是

{fi,j=fi−1,j,j<tifi,j=max(fi−1,j,fi−1,j−ti+vi)}

{fi,j=fi−1,j,j<tifi,j=max(fi−1,j,fi−1,j−ti+vi)}

 

这样就可以写出AC代码

代码#1

#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n,m;
int t[101],v[101];
int f[101][1001];
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&v[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j-t[i]>=0)//可以采
			    f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+v[i]);
			else f[i][j]=f[i-1][j];//时间不够
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

然后，我们发现，每一次只需要用到上面一层的ff，所以，我们可以用滚动数组，就开两个维度，这样...