题意：n个杯子，容量ai，已有bi的水。每次往其他杯子倒水会损失倒出水一半，问你最终只留k个杯子有水，其他杯子的水都往这k个杯子里倒，问每个k最终保留的水最大是多少。
做法：通过背包去求对于一个容量A，当此时选取留下k个杯子时，这k个杯子的最大容量是多少（直接背包即可）
然后再对于每一个k，枚举容量（选不同的杯子导致容量不同，所以需要全部枚举），去统计把剩下所有水倒入这个容量后的最大值，再输出 0.5 * (sumb - dp[i][j])+dp[i][j]，其中sumb-dp[i][j]为要倒出去的水。
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int maxn = 1e5 + 10;
int a[110], b[110], dp[110][110 * 110];
int main()
{
fastio;
int n;
cin >> n;
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
int suma = 0, sumb = 0;
for (int i = 1; i <= n; i++)cin >> a[i] >> b[i], suma += a[i], sumb += b[i];
//先去找对于一个容量A，一开始选k个能够拥有最多水的组合（其实就是一个背包）
for (int i = 1; i <= n; i++)
for (int k = i; k; k--)//k和A都需要倒着枚举
for (int A = suma; A >= a[i]; A--)
if (~dp[k - 1][A - a[i]])//从合法状态转移
dp[k][A] = max(dp[k][A], dp[k - 1][A - a[i]] + b[i]);
//统计答案
for (int i = 1; i <= n; i++)
{
double ans = 0;
for (int j = 1; j <= suma; j++)
if(~dp[i][j])
ans = max(ans, min(1.0 * j, 0.5 * (sumb + dp[i][j])));
cout << fixed << setprecision(10) << ans << " ";
}
return 0;
}