版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434623
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
01分数规划,具体可以参考博文http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html,写的非常详细且通俗易懂。
我的认识:中学里学过二分法求函数零点,其实该代码模拟的就是这种求解过程,所以只要写出目标函数,零点不难求。
接着就得到了求和式:
∑i=1n(ai−l⋅bi)≥0
\sum_{i = 1}^n (a_i - l \cdot b_i) \ge 0
要删除k个物品,当然选择贡献最小的,所以按照ai−l⋅bia_i - l \cdot b_i排序,选择n-k个物品,排除其余贡献较小的k个物品。
代码如下:
static class Pair implements Comparable<Pair>{
int a;
int b;
@Override
public int compareTo(Pair o) {
double ocmp = o.a - L * o.b;
double tcmp = this.a - L * this.b;
return ocmp == tcmp ? 0 : (ocmp > tcmp) ? 1 : -1;
}
}
static Pair[] p;
static double L;
static int k;
static int n;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
n = in.nextInt();
k = in.nextInt();
if (n == 0 && k == 0) break;
p = new Pair[n];
for (int i = 0; i < n; ++i){
p[i] = new Pair();
p[i].a = in.nextInt();
}
for (int i = 0; i < n; ++i){
p[i].b = in.nextInt();
}
double lf = 0;
double rt = 1;
while (Math.abs(rt -lf) > 1e-4){
double mid = (lf + rt) / 2;
if (!valid(mid)) rt = mid;
else lf = mid;
}
System.out.printf("%.0f\n",lf * 100);
}
}
public static boolean valid(double mid){
L = mid;
Arrays.sort(p);
double sum = 0;
for (int i = 0; i < n - k; ++i){
sum += (p[i].a - L * p[i].b);
}
return sum > 0;
}
和上一题一个思路,但此题精度要求要高很多,按照上一题的while循环,WA了,测了下,大概循环14次左右,而此题循环50次,可以达到0.000000001的精度。注意记录下下标。
代码如下:
static class Pair implements Comparable<Pair>{
int a;
int b;
int id;
@Override
public int compareTo(Pair o) {
double that = o.a - L * o.b;
double thiz = this.a - L * this.b;
return that == thiz ? 0 : (that > thiz) ? 1 : -1;
}
}
static double L;
static Pair[] p;
static int N;
static int K;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
K = in.nextInt();
p = new Pair[N];
ans = new int[K];
for (int i = 0; i < N; ++i) p[i] = new Pair();
double max = 0;
for (int i = 0; i < N; ++i){
p[i].a = in.nextInt();
p[i].b = in.nextInt();
p[i].id = i + 1;
max = Math.max(max, p[i].a / (p[i].b * 1.0 ));
}
double lf = 0.0;
double rt = max;
for (int i = 0; i < 50; ++i){
double mid = (lf + rt) / 2;
if (!valid(mid)) rt = mid;
else lf = mid;
}
for (int i = 0; i < K; ++i) ans[i] = p[i].id;
StringBuilder sb = new StringBuilder();
Arrays.sort(ans);
for (int i : ans){
sb.append(i + " ");
}
System.out.println(sb.toString().trim());
}
static int[] ans;
public static boolean valid(double mid){
L = mid;
Arrays.sort(p);
double sum = 0.0;
for (int i = 0; i < K; ++i){
sum += (p[i].a - L * p[i].b);
}
return sum > 0;
}