问题:一个旅行者有一个最多能用c公斤的背包,现在有n件物品,每件的重量分别是w1,w2,...,wn,每件的价值分别为v1,v2,...,vn,若每种物品都可无限细分,求旅行者能获得的最大总价值。
抽象:组合出价值最大的指定重量的物品。
思路:先求出每个物品的价值密度,先放入价值密度最大的物品,再放入剩余物品价值密度最大的物品,依次进行,直到背包已满。
代码:
package test;import java.util.Arrays;
/**
- 贪心法求背包问题(可分割)
- @author yanghang
*/
public class Tanxin {
public static void main(String[] args) {
/**
* 初始化
*/
// 背包的容量
double c = 12;
// 物品的数量
int n = 5;
// 物品重量数组
double[] w = new double[n];
// 物品价钱数组
double[] v = new double[n];
// 物品的重量 1,2,3,4,5
for (int i = 0; i < n; i++) {
w[i] = i + 1;
}
// 物品的价值 5,4,3,2,1
for (int i = 0; i < n; i++) {
v[i] = n - i;
}
/**
* 求出单位重量价值r[i] = v[i] / w[i]
*
*/
double[] r = new double[n];
int[] index = new int[n];
for (int i = 0; i < n; i++) {
r[i] = (double) v[i] / (double) w[i];
index[i] = i;
}
/**
* 按照价值密度排序
*/
double temp = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (r[i] < r[j]) {
temp = r[i];
r[i] = r[j];
r[j] = temp;
temp = w[i];
w[i] = w[j];
w[j] = temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
}
/**
* 初始化解向量x[n],求解并打印解向量
*/
double[] x = new double[n];
for (int i = 0; i < n; i++) {
if (w[i] <= c) {
x[i] = 1;
c = c - w[i];
} else if (w[i] > c) {
x[i] = (double)c / w[i];
c = 0;
break;
}
}
System.out.println("解向量是:" + Arrays.toString(x));
/**
* 根据解向量求出背包中存放物品的最大价值并打印
*/
double maxValue = 0;
for (int i = 0; i < n; i++) {
maxValue += v[i] * x[i];
}
System.out.println("背包中物品的最大价值为:" + maxValue);
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于