【題意】:給出n個(gè)tests,每個(gè)test有a和b兩個(gè)值,現(xiàn)要求你從這n個(gè)test中選出k個(gè)test使得這k個(gè)test中a的和除以b的和最大。

【題解】:好明顯的01分?jǐn)?shù)規(guī)劃。
               設(shè)集合x[],x[i]=0表示不選第i個(gè)test,x[i]=1表示選第i個(gè)test.
               既我們要r = (∑a[i]*x[i]) / (∑b[i]*x[i]) 最大,且∑x[i] = k.
               然后要構(gòu)造子問題,詳細(xì)的不想寫了好麻煩。
               最后上二分或者dinkelbach即可。

【代碼】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define eps 1e-6
19 #define maxn 1050
20 int n, k;
21 
22 struct Point {
23     int a, b;
24     double c;
25     bool operator <(const Point &x) const {
26         return c < x.c;
27     }
28 }p[maxn];
29 
30 double work(double l) {
31     for(int i = 0; i < n; i++) p[i].c = 1.0 * p[i].a - l * p[i].b;
32     sort(p, p + n);
33     double sum = 0.0, suma = 0.0, sumb = 0.0;
34     for(int i = k; i < n; i++) sum += p[i].c, suma += p[i].a, sumb += p[i].b;
35     return suma / sumb;
36 }
37 
38 void solve() {
39     double ans = 0.0, tmp = 0.0;
40     while(1) {
41         tmp = work(ans);
42         if(fabs(tmp - ans) < eps) break;
43         ans = tmp;
44     }
45     printf("%d\n", (int)(100.0 * (tmp + 0.005)));
46 }
47 
48 int main() {
49     while(~scanf("%d%d", &n, &k)) {
50         if(!n && !k) break;
51         for(int i = 0; i < n; i++) scanf("%d", &p[i].a);
52         for(int i = 0; i < n; i++) scanf("%d", &p[i].b);
53         solve();
54     }
55     return 0;
56 }
57