这道题MnZn用了一个十分神奇的DP+贪心的方法过掉了，个人觉得很对，但是据说要用01分数规划，望大佬帮忙看一看对不对。

大概思路：先按$t_i/w_i$排序，然后枚举$i$,用 F[i] 表示重量为 i 时最大的才艺水平，因为a/c<(a+b)/(c+d)<b/d(a/c<b/d)，每次将i后面的全部加进去就行了，用前缀和维护。

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void rd(T &x)
{
	x=0;bool f=0;char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=1;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;
}
const int N=255,M=1005;
int n,m,w[N],t[N],ord[N],dp[M],ans,sw[N],st[N];
inline bool cmp(int x,int y) {return t[x]*w[y]<t[y]*w[x];}

int main()
{
	rd(n),rd(m);
	for(int i=1;i<=m;i++) dp[i]=-1e6;
	for(int i=1;i<=n;i++) rd(w[i]),rd(t[i]),ord[i]=i;
	sort(ord+1,ord+1+n,cmp);
	for(int i=1;i<=n;i++) sw[i]=sw[i-1]+w[ord[i]];
	for(int i=1;i<=n;i++) st[i]=st[i-1]+t[ord[i]];
	for(int i=1;i<=n;i++) 
	{
		for(int j=max(m-sw[n]+sw[i-1],0);j<=m;j++)
			ans=max(ans,(dp[j]+st[n]-st[i-1])*1000/(j+sw[n]-sw[i-1]));
		for(int j=m;j>=w[ord[i]];j--)
			dp[j]=max(dp[j],dp[j-w[ord[i]]]+t[ord[i]]);
	}
	printf("%d\n",ans);
	return 0;
}

如果发现这个代码错了，请给一组Hack数据谢谢

在线等