贪心算法----物品可分割的装载问题----背包问题
-
题目
有n件物品和一个容量为m的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。
- 思路
将价值 / 重量 的比值最大的优先放入背包,所以先按比值排序,再一个个的往背包里放
- 代码
package com.algorithm;
import java.util.Arrays;
import java.util.Scanner;
class Treasure implements Comparable<Treasure>{
private double w;//每个宝物的重量
private double v;//每个宝物的价值
double p;//性价比
public double getW() {
return w;
}
public void setW(double w) {
this.w = w;
}
public double getV() {
return v;
}
public void setV(double v) {
this.v = v;
}
public double getP() {
return p;
}
public void setP(double p) {
this.p = p;
}
boolean cmp(Treasure a, Treasure b){
return a.p > b.p;//根据宝物的单位价值从大到小排序
}
@Override
public int compareTo(Treasure o) {
if(p < o.p)
return -1;
else if(p > o.p)
return 1;
else
return 0;
}
}
public class BookTest {
public static void main(String[] args) {
System.out.println("请输入宝物的数量n及背包的容量m");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//n表示有n个宝物
double m = sc.nextDouble();//m为背包的容量
System.out.println("请输入每个宝物的重量和价值,用空格分开");
Treasure[] tre = new Treasure[n];
for (int i = 0; i < n; i++){
tre[i] = new Treasure();
tre[i].setW(sc.nextDouble());
tre[i].setV(sc.nextDouble());
tre[i].setP(tre[i].getV() / tre[i].getW());
}
System.out.println("宝物按性价比从小到大排序");
Arrays.sort(tre, 0, n);
for(Treasure t : tre)//
System.out.print(t.getP() + " ");
System.out.println();
double sum = 0.0;//sum表示贪心记录运走宝物的价值之和
for (int i = n-1; i >= 0 ; i--){
//tre[i] = new Treasure();
if(m > tre[i].getW())//按照排好的顺序贪心
{
m = m - tre[i].getW();
sum += tre[i].getV();
}
else //如果宝物的重量大于背包剩下的承载力
{
sum += m * tre[i].p;//部分装入
break;
}
}
System.out.println("装入宝物的最大价值是:" + sum);
}
}
- 结果