题解 P4377 【[USACO18OPEN]Talent Show】
wenge
2019-07-29 22:58:23
我看题解全都是01分数规划和贪心，很少有背包，所以发一个不需要01分数规划，直接套裸背包的做法。
记录$dp[i][j]$为考虑前$i$头牛，选的牛才艺值总和为$j$的最小重量。
则有
$$dp[i][j]=min(dp[i-1][j],dp[i-1][j-t[i]]+w[i])(j\geq t[i])$$
$$dp[i][j]=dp[i-1][j](j<t[i])$$
边界条件：$dp[0][0]=0$，其余$dp[i][j]=\inf$
这就是一个裸的背包了。答案就是$max(\frac {i}{dp[i]})(0\leq i\leq \sum t_i,dp[i]\geq W)$。
因为背包容量$m$至多是$\sum t_i\leq250000$，二维数组会MLE。所以直接滚动数组压掉一维就可以了。
时间复杂度$O(n*\sum t_i)=O(n^2*max\ t_i)$，可以通过本题。
AC代码：
```cpp
//#pragma GCC optimize(2)
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <vector>
//int mod=1000000007;
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define clr(a,b) memset(a,b,sizeof(a));
ll w[255],t[255];
ll dp[250005];
ll n,m,k,ans;
int main(){
//ios::sync_with_stdio(false);
//cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i]>>t[i];
m+=t[i];
}
clr(dp,0x7f);
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
if(j>=t[i])dp[j]=min(dp[j],dp[j-t[i]]+w[i]);
}
}
double ans=0;
for(int i=0;i<=m;i++){
if(dp[i]>0&&dp[i]>=k)ans=max(i*1000.0/dp[i],ans);
//if(dp[i]>0&&dp[i]>=k)cout<<i<<" "<<i*1000.0/dp[i]<<"\n";
}
ll ans1=ans;
cout<<ans1;
return 0;
}
```