Pocket Gems面经prepare: Diamond and Ruby

说我有一个背包，有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个格子，直接用倒序省掉了这个维度

 1 package pg;
 2 
 3 import java.util.*;
 4 
 5 public class Ruby {
 6     
 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     }
22     
23 
24     /**
25      * @param args
26      */
27     public static void main(String[] args) {
28         // TODO Auto-generated method stub
29         int res = maxProfit(3, 10, 15, 3);
30         System.out.println(res);
31     }
32 
33 }