题目：大礼包

在LeetCode商店中，有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。

示例 1:

输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

示例 2:

输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释: 
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。

说明:

最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。

来源：力扣（LeetCode）第638题

链接：https://leetcode-cn.com/problems/shopping-offers

分析：

动态规划解法，常规解法需要使用六维数组，实在太麻烦，而且每次的维度还不一样。
使用状压dp的思想，把六维数组归为1维。
因为每一维的长度是0-6，所以我们把这7个数变为一个七进制的数字，但是把它变为10进制存在一个一维数组中。
比如111就是57，它表示a,b,c各有1个。如果是4个1，那就是a,b,c,d各有1个，然后它也有对应的十进制数。
因此，我们把needs中的数看成是一个七进制数，然后把它以十进制表示出来。
比如need如果是121，那么结果是64。那么我们就开辟一个65个的数组。最后把dp[64]返回就是最终答案了。

代码：

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int[] Decinal = {1, 7, 49, 343, 2401, 16807, 117649}; // 7的一次方，7的二次方....用于算7进制数转10进制数。
        int goods = price.size(); // 物品的总数量。
        for (int i = 0; i < goods; i++) { // 把每一个物品各买一个的情况放入大礼包中，因为大礼包不可能正好等于needs，还要添加单个买的数量。
            List<Integer> tmp = new ArrayList();
            for (int j = 0; j < goods; j++) tmp.add(0);
            tmp.set(i, 1);
            tmp.add(price.get(i));
            special.add(tmp);
        }
        int box = special.size(); // 大礼包的数量。
        int tol = change(needs, goods, Decinal); // 算出总量,比如needs是[1,2,1],那么就会算出64，也就是说有0-64个情况。[0,0,0]-[1,2,1](7进制)
        long[] dp = new long[tol+1]; // 每一种情况放在数组的相应位置。注意这里类型必须是long或以上，否则等会比大小的时候会因为过大而溢出。
        Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值。
        dp[0] = 0; // base case 0。
        for (int i = 0; i < box; i++) {
            for (int j = 0; j <= tol; j++) {
                if (!check(special.get(i), needs, j)) continue; // 检查加上这个大礼包后是不是多出去了。
                int state = change(special.get(i), goods, Decinal) + j; // 算出加上大礼包后在dp中对应的位置。
                dp[state] = Math.min(dp[state], dp[j] + special.get(i).get(goods)); // 更新dp，取最小的情况。
            }
        }
        return (int)dp[tol]; // 返回，注意强转回int类型。
    }
    
    public int change(List<Integer> sp, int n, int[] Deci) { // 把7进制数变为10进制数。
        int res = 0;
        for (int i = 0; i < n; i++) res += sp.get(i) * Deci[i]; // 7变10公式,sp[i] * 7 ** i,i从0开始。
        return res;
    }
    
    public boolean check(List<Integer> sp, List<Integer> needs, int cur) { // 检查数量是否小于needs。
        for (int i = 0; i < sp.size() - 1; i++) {
            if (cur % 7 + sp.get(i) > needs.get(i)) return false;//7进制最左边一位就是a物品的数量，加上当前大礼包后和needs的a物品数量进行比较
            cur /= 7; // 相当于向右移一位，那么a物品就没了，最左边的变成了b物品。
        }
        return true;
    }

}