一共有n个文件，每个文件大小为c[i]，价值为w[i]
U盘大小为S，传输端口大小为L，求最小的传输端口L使得U盘总文件价值不小于p
1. 二分 + 动态规划
端口只是限制了可选的文件，去掉这个限制后，原问题是0-1背包问题
void maxval(int n,int p,int S,vector<int>&c,vector<int>&w){
int left = 1; int right = 1e4;
int dp[S+1];
while(left<right){
int res = 0;
memset(dp,0,sizeof(dp));
int mid = (left+right)/2;
for(int i=0;i<n;i++){
if(c[i]>mid) continue;//跳过
for(int j=S;j>=c[i];j--){
dp[j] = max(dp[j],dp[j-c[i]]+w[i]);
res = max(res,dp[j]);
}
}
if(res>=p) right = mid;
else left = mid + 1;
}
if(right == 1e4) cout<<"No Solution!";
else cout<<right;
}