题目描述
有(n)个物品，每个物品有一个体积(v_i)，背包容量(s)。要求选一些物品恰好装满背包且物品个数最少，并在这样的方案中：
（1）求出中位数最小的方案的中位数（(k)个元素的中位数是从小到大第(⌊k/2⌋)个数）；
（2）求出众数最小的方案的众数；
（3）求出极差最小的方案的极差。
解题思路
令每个物品价值为1，求装满时的最小价值，这只需01背包即可，答案即为最小个数(m)。
对于众数，二分答案并删去多余物品即可。
对于中位数，二分答案，令每个物品价值为(inf+t)，其中体积大于二分的答案时(t)为1，否则为-1。同样求出装满时最小价值，若超过(m imes inf)则真正答案更大，否则更小。正确性是因为任意时刻，(dp_i)保存的值若要求最优，首先要保证取的个数是最少的（否则没有意义），在此条件下尽可能少取体积大的物品。而全局最优答案必然由局部最优答案转移（可反证）。
对于极差，考虑从小到大加入物品，每个物品价值(inf)，但是若该物品第一次加入背包则价值(inf-v_i)。每加完一个物品(i)更新完(dp)后，求(dp_s+v_i)。所有值取最小即可。
时间复杂度(O(ns log n))
一些感受
根据以上思路，除了极差部分可全部转化为普通01背包，大大减小了代码量（仅60行）。极差部分也非常好写，详见代码。
可惜比赛时没想出来！赛后过了若干天补题时想了一会就出来了（生气~）。最后，这道题质量真是太高啦！“题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！”
AC代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 #define MAXV 5001 6 #define INF 10001 7 int dp[MAXV]; 8 int v[5001], c[5001]; 9 int solve(int n, int s) 10 { 11 memset(dp, 0x3f, sizeof(dp)); 12 dp[0] = 0; 13 for (int i = 0; i < n; i++){ 14 for (int j = s; j >= v[i]; j--) 15 dp[j] = min(dp[j], dp[j - v[i]] + c[i]); 16 } 17 return dp[s]; 18 } 19 int solve2(int n, int s) 20 { 21 memset(dp, 0x3f, sizeof(dp)); 22 dp[0] = 0; 23 int ans = 0x3fffffff; 24 for (int i = 0; i < n; i++){ 25 for (int j = s; j > v[i]; j--) 26 dp[j] = min(dp[j], dp[j - v[i]] + INF); 27 dp[v[i]] = min(dp[v[i]], INF - v[i]); 28 ans = min(ans, dp[s] + v[i]); 29 } 30 return ans % INF; 31 } 32 int main() 33 { 34 int n, s; 35 scanf("%d%d", &n, &s); 36 for (int i = 0; i < n; i++){ 37 scanf("%d", &v[i]); 38 c[i] = 1; 39 } 40 sort(v, v + n); 41 int num = solve(n, s), l, r; 42 if (num > n){ printf("-1"); return 0; } 43 printf("%.9lf ", (double)s / num); 44 for (l = 0, r = n - 1; l != r;){ 45 int mid = (l + r) >> 1, w = v[mid]; 46 for (int i = 0; i < n; i++) 47 c[i] = INF + (v[i] > w ? 1 : -1); 48 if (solve(n, s) > INF * num)l = mid + 1; 49 else r = mid; 50 } 51 printf("%d ", v[l]); 52 for (l = 1, r = n; l != r;){ 53 int mid = (l + r) >> 1; 54 for (int i = 0, j; i < n; i++){ 55 j = !i || v[i] != v[i - 1] ? 1 : j + 1; 56 c[i] = j <= mid ? 1 : INF; 57 } 58 if (solve(n, s) > num)l = mid + 1; 59 else r = mid; 60 } 61 printf("%d ", l); 62 printf("%d", solve2(n, s)); 63 return 0; 64 }