RPG game：勇者斗恶龙之宝藏背包

最开始被题目表象骗了，还以为是背包问题，但好像实际上也可以用背包做，虽然我不知道怎么做。写了一种最朴素的解法，解释都在注释里面，题目帖子里面讲了，至于topK的解法我也不想深究了，毕竟PG还有很多其他难题要准备。

package PocketGem;

import java.util.HashMap;

/**
 * Created by yuanfanz on 17/7/28.
 */
public class Treasure {
    static class Tuple {
        String name;
        int value;
        int maximum_stack_size;

        public Tuple(String name, int value, int maximum_stack_size) {
            this.name = name;
            this.value = value;
            this.maximum_stack_size = maximum_stack_size;
        }
    }

    public static int maxValue(int n, String[] items, Tuple[] item_infos) {
        int val = 0;
        HashMap<String, Integer> maxMap = new HashMap<>();
        HashMap<String, Integer> valMap = new HashMap<>();
        HashMap<String, Integer> countMap = new HashMap<>();

        // max_stack_size 代表一个stack能放当前item的最大数量

        for (Tuple item_info : item_infos) {
            maxMap.put(item_info.name, item_info.maximum_stack_size);
            valMap.put(item_info.name, item_info.value);
        }
        for (String item : items) {
            countMap.put(item, countMap.getOrDefault(item, 0) + 1);
        }

        // 对于每一个stack都遍历一下看看能不能放item
        // 暴力解，每一个stack下面，遍历每一个countMap中的item去找能放入的最大价值的item
        for (int i = 0; i < n && !countMap.isEmpty(); i++) {
            // max是当前stack的总价值
            int max = 0;

            // select用来表示我们选择的item
            String select = "";

            // num是当前item放入stack的数量
            int num = 0;
            for (String item : countMap.keySet()) {
                int count = countMap.get(item);

                // 如果一个item的总数量大于它在stack能放的最大数量，我们直接装满

                if (count >= maxMap.get(item)) {

                    // 如果装满之后，总价值大于之前stack的总价值，更新
                    if (maxMap.get(item) * valMap.get(item) > max) {
                        select = item;
                        num = maxMap.get(item);
                        max = maxMap.get(item) * valMap.get(item);
                    }
                } else {

                    // 同样，如果装完之后，总价值大于之前stack的总价值，更新
                    if (count * valMap.get(item) > max) {
                        select = item;
                        num = count;
                        max = count * valMap.get(item);
                    }
                }
            }
            // 每次都把一个stack上面的最大价值max加到总价值上面
            val += max;

            // 如果select，也就是选择的item不为空，也就是我们更新了当前stack选择的item
            // 所以要把countMap里面的数量更新，我们已经把一定数量（num）的item放入了背包
            if (!select.equals("")) {
                countMap.put(select, countMap.get(select) - num);

                // 如果该item已经取完了，我们把它移出map
                if (countMap.get(select) == 0) {
                    countMap.remove(select);
                }
            }
        }
        return val;
    }

    public static void main(String[] args) {
        // write your code here
        Tuple[] tuples = new Tuple[3];
        tuples[0] = new Tuple("diamond", 10, 5);
        tuples[1] = new Tuple("ruby", 5, 5);
        tuples[2] = new Tuple("armor", 25, 1);
        String[] items = {"diamond", "ruby", "armor", "diamond", "diamond", "ruby", "diamond", "diamond", "diamond", "diamond",
                "diamond", "armor"};
        System.out.println(maxValue(3, items, tuples));

    }
}