算法描述
已知道n种物品和一个可容纳c重量的背包，第i种物品的重量为wi，价值为pi，装包的时候可以把物品拆开（即可只装每种物品的一部分），设计如何装包，使装包所得整体的价值最高？
算法思路
首先，我们要知道，n种物品以及他们对应的价值，都是由用户输入的
我们使用贪心算法，每一步取最大效益的物品放入背包之中（及单位价值为最高的物品 单位价值=pi/wi）
由以上思路，我们可以定义一个二维数组来接收用户输入的数值
w[i][0] 代表了第i种物品的重量（即wi）w[i][1] 代表了第i种物品的价值（即pi）w[n][m] n范围为1~n m范围为0~1
这里需要注意，数组下标是从0开始的，我们的n是从1开始的，空出了一个0，所以我们定义n应该定义为n+1 这里应该不难理解，n+1的话，下标就是0~n，我们需要1~n这n个位置
定义为
double[][] w = new double[n+1][2]除了上面所说，我们还需一个
Flag类来存放单位价值以及该单位价值对应的第i个物品（也就是下标）我们将单位价值计算得出后作为
Flag类的成员变量content,以及下标作为Flag类中的成员变量flag，之后使用ArrayList存放多个Flag类之后，将单位价值存放在一个一维数组中，使用排序，从小到大排序
得到排序之后的一维数组，依次与
ArrayList中的每一个Flag类的content作比较，得到其对应的下标，存入到栈中之后，栈顶就是单位价值最大的所对应的下标，依次取出来（即实现了每次都是取到的物品都是单位价值最大的），进行相关的运算即可
算法实现
Scanner scanner = new Scanner(System.in);
double cost = 0;//记录当背包满的时候所达到的价值
System.out.println("输入物品个数n:");
int n = scanner.nextInt();
System.out.println("输入背包可装容量c:");
double c = scanner.nextDouble();
double temp[] = new double[n+1];
double w[][] = new double[n+1][2];
ArrayList<Flag> list = new ArrayList<Main.Flag>();
for(int i=1;i<=n;i++){
System.out.println("w"+i+"重量:");
w[i][0] = scanner.nextDouble();
System.out.println("w"+i+"价值:");
w[i][1] = scanner.nextDouble();
temp[i]=w[i][1]/w[i][0];
}
scanner.close();
Stack<Integer> stack = new Stack<Integer>();
//存入到list中，保存原来的下标和内容
for(int i=1;i<temp.length;i++){
Flag flag = new Flag(i, temp[i]);
list.add(flag);
}
double t = 0;
Arrays.sort(temp);//使用java中自带的快速排序
//将原来的下标存入进栈中，处于栈顶的是单位价值最高的该物品的下标
for(int i=1;i<temp.length;i++){
for(Flag flag : list){
if(flag.getContent()==temp[i]){
stack.push(flag.getFlag());
}
}
}
while(!stack.isEmpty()){
int i =stack.pop();//出栈
c = c -w[i][0];
if(c<=0){
c = c+w[i][0];//加回之前所减去的内容，计算百分比
double a = (c/w[i][0])*100;
DecimalFormat format = new DecimalFormat("##.#");
System.out.println("装入"+"第"+i+"种物品的百分之"+format.format(a)+"，重量为"+w[i][0]+"，价值为"+w[i][1]);
cost = cost+w[i][1]*(a/100);
System.out.println("最大价值为"+format.format(cost));
break;
}else{
cost = cost+w[i][1];
}
System.out.println("装入"+"第"+i+"种物品"+"，重量为"+w[i][0]+"，价值为"+w[i][1]);
}
}
//定义了一个Flag类，存放原来的坐标以及单位价值
public static class Flag{
int flag;
double content;
public Flag(int flag,double content){
this.flag = flag;
this.content= content;
}
public int getFlag(){
return this.flag;
}
public double getContent(){
return this.content;
}
} 结果
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
