题目大意：
你有n个杯子，你可以把一个杯子里面的水倒到另外一个杯子，假设倒出来 (x) 的水，那么 (x/2) 的水会倒在桌子上，只有 (x/2) 的水会进入杯子， (x) 可以是一个实数，问最后选择 (k) 个杯子，杯子中的水最多是多少。
题解：
一开始感觉好难，后来仔细思考发现是一个很简单的 (dp) 问题
(dp[j][k]) 表示选择了j个物品，还剩下k的空间，获得的最大价值。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int dp[maxn][maxn*maxn];
// dp[j][k] 表示选择了j个物品，还剩下k的空间，获得的最大价值。
int a[maxn],b[maxn];
double ans[maxn];
int main(){
int n,sum = 0,S = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),sum+=a[i] - b[i],S += b[i];
memset(dp,0xef,sizeof(dp));
dp[0][0] = 0;
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
for(int k=sum;k>=0;k--){
int val = a[i] - b[i];
if(k>=val) dp[j][k] = max(dp[j][k],dp[j-1][k-val]+b[i]);
// printf("i = %d j = %d k = %d %d
",i,j,k,dp[j][k]);
}
}
}
for(int j=1;j<=n;j++){
for(int k=0;k<=sum;k++){
double val = min(k*1.0,(S-dp[j][k])*1.0/2);
ans[j] = max(ans[j],1.0*dp[j][k]+val);
}
printf("%.10f",ans[j]);
if(j==n) printf("
");
else printf(" ");
}
return 0;
}