Diamond and Ruby - Pocket Gems prepare

https://www.1point3acres.com/bbs/thread-217589-1-1.html
You’re playing your favorite RPG, and your character has just found a room full of treasure. You have n inventory slots. Luckily, objects of the same type stack together, with the maximum size of the stack depending on the type (e.g. coins might stack to 10, diamonds to 5, armor to 1, etc.). Each stack (or partial stack) takes up 1 inventory slot. Each item has a selling value (e.g. a single diamond might be worth 10, so a stack of 5 diamonds would be worth 50). You want to maximize the total selling value of the items in your inventory.

1. class Tuple{
2.     String name;
3.     int value;
4.     int maximum_stack_size;
5.     public Tuple(String name, int value, int maximum_stack_size){
6.         this.name = name;
7.         this.value = value;
8.         this.maximum_stack_size = maximum_stack_size;
9.     }
10. }
11. 
    
12. public class Main {
13. 
    
14.     public static int maxValue(int n, String[] items, Tuple[] item_infos){
15.         int val = 0;
16.         HashMap<String, Integer> maxMap = new HashMap<>();
17.         HashMap<String, Integer> valMap = new HashMap<>();
18.         HashMap<String, Integer> countMap = new HashMap<>();
19.         for (Tuple item_info : item_infos){
20.             maxMap.put(item_info.name, item_info.maximum_stack_size);
21.             valMap.put(item_info.name, item_info.value);
22.         }
23.         for(String item : items){
24.             countMap.put(item, countMap.getOrDefault(item, 0) + 1);
25.         }
26.         for(int i = 0; i < n && !countMap.isEmpty(); i++){
27.             int max = 0;
28.             String select = "";
29.             int num = 0;
30.             for (String item : countMap.keySet()){
31.                 int count = countMap.get(item);
32.                 if(count >= maxMap.get(item)){
33.                     if(maxMap.get(item) * valMap.get(item) > max) {
34.                         select = item;
35.                         num = maxMap.get(item);
36.                         max = maxMap.get(item) * valMap.get(item);
37.                     }
38.                 }
39.                 else{
40.                     if (count * valMap.get(item) > max){
41.                         select = item;
42.                         num = count;
43.                         max = count * valMap.get(item);. From 1point 3acres bbs
44.                     }
45.                 }
46.             }
47.             val += max;
48.             if(!select.equals("")){
49.                 countMap.put(select, countMap.get(select) - num);. 1point3acres
50.                 if (countMap.get(select) == 0){
51.                     countMap.remove(select);
52.                 }. 1point3acres
53.             }. From 1point 3acres bbs
54.         }
55.         return val;
56.     }

我的理解是，对于每个item，可以用总的个数除以一个stack最多能放的个数，得到放满的stack个数，并算这些stack的value，并且丢到heap里面，然后再算余数对应stack的value，丢到heap里去，最后取top k...我不明白的事....这么算复杂度真的有优化么？假设k很小，item很多...岂不是做了很多没必要的维护堆的操作？sift up/sift down

突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的)一遍. 而heap的做法,复杂度是O(nlog(k)),只用遍历一遍, 然后存入一个大小为k的heap就完事了. 不知道我的想法有没有道理.

1. public static int maxValue(int n, String[] stuff, item[] items ){
2.         Map<String, Integer> cntMap = new HashMap<String,Integer>();
3.         for(String s:stuff){
4.             cntMap.put(s,cntMap.getOrDefault(s,0)+1);
5.         }
6.         PriorityQueue<Integer> maxHeap = 
7.                          new PriorityQueue<>((x,y)->(y-x));
8.         Map<String, item> itemMap = new HashMap<String, item>();
9.         for(item i: items){
10.             itemMap.put(i.name, i);
11.         }
12.         
13.         for(String key: cntMap.keySet()){
14.             int amt = cntMap.get(key);
15.             int maxStack = itemMap.get(key).max_stack;
16.             int value = itemMap.get(key).value;. check 1point3acres for more.
17.             if(amt>maxStack){
18.                 maxHeap.add(value*maxStack);. From 1point 3acres bbs
19.                 maxHeap.add(value*(amt-maxStack));
20.             }else{
21.                 maxHeap.add(value*amt);
22.             }
23.             
24.         }
25.         int t=0, rlt = 0;-baidu 1point3acres
26.         while(t<n){
27.             rlt+=maxHeap.poll();
28.             t++;
29.         }
30.         return rlt;
31.         . 1point3acres
32.     }

http://www.cnblogs.com/EdwardLiu/p/6423891.html

说我有一个背包，有n个格子，一个格子可以放5个钻石，一个钻石10块钱，一个格子可以放5个ruby，一个ruby 5块钱， 一个格子可以放一个装备，一个装备25块钱。
然后给你n个钻石n个ruby n个装备，求最大化收益。

类似Ones and Zeroes

Dp[i][j][k] = Max(dp[i-5][j][k] + 5*10,    dp[i][j-5][k] + 5*5,    dp[i][j][k-1] + 1*25)

reduce了dimension，其实还有一个维度是前k个格子，直接用倒序省掉了这个维度

 7     public static int maxProfit(int n, int a, int b, int c) {
 8         int[][][] dp = new int[a+1][b+1][c+1];
 9         for (int l=1; l<=n; l++) {
10             for (int i=a; i>=0; i--) {
11                 for (int j=b; j>=0; j--) {
12                     for (int k=c; k>=0; k--) {
13                         if (i >= 5) dp[i][j][k] = Math.max(dp[i][j][k], dp[i-5][j][k] + 5*10);
14                         if (j >= 5) dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j-5][k] + 5*5);
15                         if (k >= 1) dp[i][j][k] = Math.max(dp[i][j][k], dp[i][j][k-1] + 1*25);
16                     }
17                 }
18             }
19         }
20         return dp[a][b][c];
21     }