分析
经典的01分数规划问题
用01背包check即可
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
struct node {
int w,t;
};
node d[1100];
int dp[1100000],n,m;
inline bool go(int mid){
int i,j,k;
memset(dp,-0x3f,sizeof(dp));
dp[0]=0;
for(i=1;i<=n;i++)
for(j=m;j>=0;j--)
dp[min(m,j+d[i].w)]=
max(dp[j]+d[i].t-d[i].w*mid,dp[min(m,j+d[i].w)]);
return dp[m]>=0;
}
signed main(){
int i,j,s1=0,s2=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d",&d[i].w,&d[i].t);
d[i].t*=1000;
}
int le=0,ri=1000001;
while(ri-le>1){
int mid=(le+ri)>>1;
if(go(mid))le=mid;
else ri=mid;
}
cout<<le;
return 0;
}