题目
有n个物体,第i个物体的重量为wi,价值为vi。在总重量不超过C的情况下让总价值尽量高。每一个物体都可以只取走一部分,价值和重量按比例计算。
注意:每个物体可以只拿一部分,因此一定可以让总重量恰好为C。
input
C=10
w=1,2,3,4,5
v=2,4,3,1,4
output
13.2
分析
还是利用打包思维 类似c的结构体 把 w v price 绑定一起 并对price排序来选择 价值最高的
在计算price的时候是 double类型 所以 我们在判断大小的排序的时候 要注意
代码
package BlueCup.Eight_DP_greed;
import java.util.Scanner;
import static java.util.Arrays.sort;
public class 部分背包问题 {
public static void main(String[] args) {
// Scanner cin = new Scanner(System.in);
double C = 10;//总重量
int[] w = {1, 2, 3, 4, 5};
int[] v = {3, 4, 3, 1, 4};
Obj[] obj = new Obj[5];
for (int i = 0; i < 5; i++) {
obj[i] = new Obj(w[i], v[i]);
}
sort(obj);//按照(价值)排序(升序)
f(C, obj);
}
private static void f(double c, Obj[] obj) {
double maxValue = 0;
for (int i = obj.length - 1; i >= 0; i--) {//逆序遍历
if (obj[i].w <= c) {//重量够 最大价值
c -= obj[i].w;
maxValue += obj[i].v;
} else { //剩下的c不够最大价值 要且 (c/w)是需求/总量
maxValue += (c / obj[i].w) * obj[i].v;
break;
}
}
System.out.println(maxValue);
}
public static class Obj implements Comparable<Obj> {
double w;
double v;
public Obj(double w, double v) {
this.w = w;
this.v = v;
}
public double getPrice() {//求价值
return v / (double)w;
}
@Override
public int compareTo(Obj o) {
if (this.getPrice() < o.getPrice()) {
return -1;
} else if (this.getPrice() > o.getPrice()) {
return 1;
} else
return 0;
}
//DeBUG
@Override
public String toString() {
return "Obj{" +
"w=" + w +
", v=" + v +
",Price"+getPrice()+
'}';
}
}
}
本文作者:Author: 寒光博客
文章标题:部分背包问题 经典贪心
本文地址:https://dxoca.cn/Algorithm/251.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/251.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。