题目描述
玥玥带乔乔一起逃亡，现在有许多的东西要放到乔乔的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品。现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，乔乔会非常感谢你。
输入描述:
第1行有2个整数，物品种数n和背包装载体积v；
第2行到i+1行每行3个整数，为第i种物品的数量m、体积w、价值s。
输出描述:
仅包含一个整数，即为能拿到的最大的物品价值总和。
示例1
输入
2 10
3 4 3
2 2 5
输出
13(重量：2+2+4 价值：5+5+3)
思路
这是一个很典型的背包问题，可以用贪心来解决
1、要找到局部最优的解，这道题贪心算法第一步是先排序，题目是要最大价值，那么我们就用单位价值量来决定先把谁放在背包里，单位价值越高就先进入背包。
2、将题目给定的条件转化为三个数组n[] v[] w[]，很明显v/w就是单位价值，根据这个来排
3、将排好序的单位价值拿出来，这里记得要记录下之前的索引位置，将背包装载，减去数量，减去背包剩余容量
4、记得是可以往下搜索的，如果当前最大的单位价值的重量过大，剩余容量过小，是可以继续往下走的。举个例子，现在背包剩余容量是1，而我搜索到的单位价值量最高的物体重量是2，明显装不进去，这时候我们不能直接退出，而是要继续往下，如果找到了一个重量是1的就装入背包，找到最后没有找到则返回答案
思维导图
参考代码
/**
* 0-1背包问题
* 给定三个数组：n[] v[] w[]
* 创建四个arralist Keys（按顺序存放w/v的值）Values（按顺序存放对应的索引）keys（对Keys排序后的w/v）values（对应的索引）
* 第一步：根据w/v（单位重量的价值）来排序------用Keys和Values转化为有顺序的keys和values
* 第二步：根据values记录的索引值寻找最优化的选择，每次往背包加入物品
*/
import java.io.*;
import java.util.*;
public class Main{
/**
* 题目前提：有三个数组分别是数量n[] 重量w[] 价值v[]
* 这里首先用四个ArrayList来存数据，其实一开始觉得map集合的key-value形式好像更适合这种储存方式
* 我的想法是将单位重量的大小与索引值即v/w - i，这样的形式存储，方便之后对v/w排序后仍然能找到之前的索引值--这个索引值对应着n/w/v三个数组
*
* 遇到的一个问题是用了三种map集合，HashMap、TreeMap、以及LinkedHashMap，问题出现在这三种集合有些特殊的性质
* HashMap和TreeMap底层是散列表或二叉树，他是key无序无重复value无序可重复的，无序指的是存入数据与取出数据不一样
* LinkedHashMap是有序不可重复
*
* 因此最后我用四个ArrayList来操作
*/
static ArrayList<Double> Keys = new ArrayList<Double>();
static ArrayList<Integer> Values = new ArrayList<Integer>();
static ArrayList<Double> keys = new ArrayList<Double>();
static ArrayList<Integer> values = new ArrayList<Integer>();
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
String[] values1 = str.split(" ");
int number = Integer.parseInt(values1[0]);
int weight = Integer.parseInt(values1[1]);//number是数量 weight是背包容量
int ans = 0;
int[] n = new int[number];
int[] w = new int[number];
int[] v = new int[number];//创建三个数组，存数量 重量 价值
int index=0;
//---------------------------------
//以上是数据输入以及创建数组部分
StringBuilder sb1 =new StringBuilder("");//价值累加过程
StringBuilder sb2 = new StringBuilder("");//背包装载过程
for(int i=0;i<number;i++){//对三个数组填充数据n/v/w，数据输入完毕，准备填充四个ArrayList
str = br.readLine();
String[] values2 = str.split(" ");
n[index] = Integer.parseInt(values2[0]);
w[index] = Integer.parseInt(values2[1]);
v[index++] = Integer.parseInt(values2[2]);
}
double key[] = new double[number];//key在这里用两个数组v和w来计算并存储了单位重量的价值
for(int i=0;i<number;i++){
key[i] = (double)v[i]/(double)w[i];
}
for (int i = 0; i < number; i++) {//填充前两个ArrayList Keys和Values
Keys.add(key[i]);
Values.add(i);
}
//---------------------------------
//以上完成了三个数组n/w/v 以及 单位价值Keys 和 相应索引Values的填充，接下来进行排序
System.out.println("起始数据");
System.out.println(Keys);
System.out.println(Values);
fun();//fun实际上用来排序，出现一个排好序的从大到小的 单位价值keys 和 相应索引values
System.out.println("单位价值总量排序");
System.out.println(keys);
System.out.println(values);
//---------------------------------
//以上完成了单位价值的排序，接下来可以使用贪心一点一点装载背包
index = 0;//index是由0开始到size
while (index<values.size()){
int index2 = values.get(index);// 0 -- > values(0)就是找到第一个最大的单位价值的索引位置
if(weight-w[index2]>=0&&n[index2]>0){//如果背包装得下，并且现在物体的数量n大于0
System.out.println("拿到了"+"数量为"+n[index2]+"重量为"+w[index2]+"价值为"+v[index2]+"的物品"+" 背包剩余容量"+weight);
ans += v[index2];//价值增加
weight-=w[index2];//背包剩余容量减少
n[index2]--;//数量减一
sb1.append(v[index2]+"\t");
sb2.append(weight+"\t");
}else{
index++;
}
}
sb1.append("\n");
sb2.append("\n");
System.out.println("背包过程");
System.out.println(sb1.toString()+sb2.toString());
System.out.println("最终结果："+ans);
}
public static void fun(){
int len = Keys.size();//O（n²）的排序，每次拿出最大值
for (int i = 0; i < len; i++) {
Double max = new Double(0);
Integer number = new Integer(0);
for (int j = 0;j<Values.size();j++){
if (Keys.get(j).compareTo(max)>0){
max = Keys.get(j);
number = Values.get(j);
}
}
keys.add(max);
values.add(number);
Values.remove(Keys.indexOf(max));
Keys.remove(max);
}
}
}程序的输出结果
输入数据
输出
......
京公网安备 11010502036488号