2020-09-13 背包问题的贪心算法

题目描述
玥玥带乔乔一起逃亡，现在有许多的东西要放到乔乔的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品。现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，乔乔会非常感谢你。
输入描述:
第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);
        }
    }
}

程序的输出结果
输入数据

输出


......