/**
给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大
选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以它局部最优满足全局最优,可以用贪心法解决。
首先计算每种物品单位重量的价值V/W,然后按单位重量价值从大到小进行排序,根据贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。或将这种物品全部装入背包后,背包内的物品总重量未超过背包容量,则选择单位重量价值次高的物品并尽可能多地装入背包,依此策略一直进行下去,直到背包装满为止。
*/
class Demo1 {
public static void main(String[] args){
Object p1 = new Object();
Object p2 = new Object();
Object p3 = new Object();
Object p4 = new Object();
Method m = new Method(p1,p2,p3,p4);
p1.chushihua(3,4);
p2.chushihua(2,3);
p3.chushihua(2,5);
p4.chushihua(4,5);
m.sortObject(m.arr,4);
m.knaspsack(m.arr,4);
m.print(m.arr,4);
}
}
class Object{
int value;
int weight;
float avevalue;
float num;
void chushihua(int value,int weight){
this.value = value;
this.weight = weight;
this.avevalue = ((float)value/(float)weight);
}
}
class Method extends Object{
Object arr[] = new Object[4];
Method(Object p1,Object p2,Object p3,Object p4){ //将4个物品引用存放在一个数组中
arr[0] = p1;
arr[1] = p2;
arr[2] = p3;
arr[3] = p4;
}
void sortObject(Object a[],int n){ //按物品平均价值排序,n为物品个数
for(int i = 0;i < n-1; i++){
for(int j = 0;j < n-i-1; j++){
if(a[j].avevalue < a[j+1].avevalue){
Object temp;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
void knaspsack(Object b[],int n){
//v为背包容量,n为物品数
int c = 15; //背包容量
for(int i = 0;i < n; i++){
b[i].num = 0;
if(b[i].weight > c){
b[i].num = (float)c/(float)(b[i].weight);
break;
}
else{
b[i].num = 1;
c -= b[i].weight;
}
}
}
void print(Object c[],int n){
for(int i = 0;i < n; i++){
System.out.println("价格为"+c[i].value+","+"重量为"+c[i].weight+"的物品放入"+c[i].num+"件");
}
}
}