Yougth現在有n個物品的重量和價值分別是Wi和Vi,你能幫他從中選出k個物品使得單位重量的價值最大嗎?
3 2 2 2 5 3 2 1
0.75
/* *二分搜索+貪心選擇 *二分搜索:首先,你得知道k個(任意個)物品的單位價值不超過的最大的單個物品的單位價值,自己想想就明白了 * 所以ans(假定為最終答案)必定在0-最大單個物品的單位價值之間,我們可以用二分法來不斷縮小區間范圍 直至精度達到要求。至於如何決定區間范圍是往左邊還是往右邊縮小,就需要對當前答案進行判斷,判斷是否存在一種方案 可以使得k個物品的單位價值不低於當前答案,判斷方案存在與否需要用到貪心選擇 *貪心選擇:(v1+v2+...+vk)/(w1+w2+...+wk)>=cur_ans(即當前答案) * 將這個式子轉化成:(v1-cur_ans*w1) + (v2-cur_ans*w2) + .. (vk-cur_ans*wk) >= 0 * 至此,可以看出我們可以對vi-cur_ans*wi組成的數組進行非遞增排序,選出前k個作為方案 */ #includeusing namespace std; #include #include #include #include #include #define eps 1e-3 #define MAXN 10005 int n,k; double v[MAXN],w[MAXN]; int check(double x) { double a[MAXN]; for (int i = 0; i < n; ++i) { a[i] = v[i] - x*w[i]; } sort(a,a+n); reverse(a,a+n); double sum = .0; for (int i = 0; i < k; ++i) { sum += a[i]; } return (sum >=0) ? 1 : 0; } double fenzhi(double right) { double l = 0, r = right; while (r - l > eps) { double mid = (l+r)/2; if (check(mid)) { l = mid; } else { r = mid; } } return l; } int main() { while (cin >> n >> k) { double right = -1; for (int i = 0; i < n; ++i) { cin >> w[i] >> v[i]; right = max(right,v[i]*1.0/w[i]); } printf(%.2lf ,fenzhi(right)); } return 0; }