传送门——P2370 yyy2015c01 的 U 盘

题解：题目意思很好理解，就是说，当能够达到预期的U盘的最小接口（接口越大，能传递的文件越大），然后我们就需要先看题目了，有n个文件，每个文件有其自己的重量和价值，我们的U盘最多就只能装S大小的文件，因此我们很容易就想到了01背包，但是和01背包不同的地方就我们会有一个对文件重量的限制，不允许超过L，那我们该如何去得到这个最小的L呢，我们不难想到二分答案，我们对文件的大小进行排序，然后二分，如果算出来的价值小了，就向右取，如果价值大于预期，就向左取，然后循环往复，用ans去记录能够达到预期的的最小的接口大小L

注意：每次进行二分操作的时候都要重新初始化dp数组，还有就是在进行01背包的时候需要对文件的大小进行筛选，大于接口大小的都要去跳过 

//二分答案枚举文件大小，价值就将接口减小，小于价值就将接口增大 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,s;
struct node
{
	int w;
	int v;
}a[1005];
int dp[1005];//表示大小为j内存的u盘能保留的最大价值
int L;//限制传送的最大文件 
int ans;//用来记录可行的数值 
bool cmp(node a,node b)
{
	return a.w<b.w;
}

signed main()
{
	cin>>n>>p>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].w>>a[i].v;
	}
	sort(a+1,a+1+n,cmp);
	int l=1,r=n;
	int mid=0;
	int flag=0;
	while(l<=r)
	{
		memset(dp,0,sizeof(dp));
		
		mid=(l+r)>>1;
		L=a[mid].w;
		for(int i=1;i<=n;i++)
		{
			if(a[i].w>L)
			continue;
			
			for(int j=s;j>=a[i].w;j--)
			{
				dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
			}
		}
		if(dp[s]>=p)
		{
			ans=L;
			r=mid-1;
			flag=1;
		}
		else
		{
			l=mid+1;
		}
	}
	if(flag==0)
	{
		cout<<"No Solution!";
		return 0;
	}
	cout<<ans;
	return 0;
}