LeetCode 638. 大礼包（分组背包）

大礼包（分组背包）"/>

LeetCode 638. 大礼包（分组背包）

在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个。
你不可以购买超出待购清单的物品，即使更便宜。

思路：
分组背包裸题不解释

class Solution {
public:int dp[7][7][7][7][7][7];int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {while(needs.size() < 6) needs.push_back(0);int now[6];memset(dp,0x3f,sizeof(dp));dp[0][0][0][0][0][0] = 0;for(int i = 0;i < price.size();i++) {vector<int>now;for(int j = 0;j < i;j++) {now.push_back(0);}now.push_back(1);for(int j = i + 1;j < 6;j++) {now.push_back(0);}now.push_back(price[i]);special.push_back(now);}for(int i = 0;i < special.size();i++) {int num = special[i].back();special[i].pop_back();while (special[i].size() < 6) {special[i].push_back(0);}special[i].push_back(num);}for(int i = 0;i < special.size();i++) {for(now[0] = special[i][0];now[0] <= needs[0];now[0]++) {for(now[1] = special[i][1];now[1] <= needs[1];now[1]++) {for(now[2] = special[i][2];now[2] <= needs[2];now[2]++) {for(now[3] = special[i][3];now[3] <= needs[3];now[3]++) {for(now[4] = special[i][4];now[4] <= needs[4];now[4]++) {for(now[5] = special[i][5];now[5] <= needs[5];now[5]++) {int flag = 0;for(int j = 0;j < 6;j++) {if(now[j] < special[i][j]) flag = 1;}if(flag) continue;dp[now[0]][now[1]][now[2]][now[3]][now[4]][now[5]] = min(dp[now[0]][now[1]][now[2]][now[3]][now[4]][now[5]],dp[now[0] - special[i][0]][now[1] - special[i][1]][now[2] - special[i][2]][now[3] - special[i][3]][now[4] - special[i][4]][now[5] - special[i][5]] + special[i][6]);}}}}}}}return dp[needs[0]][needs[1]][needs[2]][needs[3]][needs[4]][needs[5]];}
};