本文共 3596 字，大约阅读时间需要 11 分钟。

1. 题目

在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） 链接：https://leetcode-cn.com/problems/shopping-offers

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 状态压缩超时解

• 思路是，把int看做买东西的个数的状态，3个位最大是7，题目说不超过6，物品也不超过6，最多18位就可以了
• 一个int就可以存下买的物品的个数
• 最后一个例子超时，可能这个最大的状态数太大了

class Solution {
   	int n;public:    int shoppingOffers(vector
   
    & price, vector
    
     
      >& special, vector
      
       & needs) {
       	n = price.size();    	int i, j, k, target = 0, num, newstate;    	for(i = 0; i < n; ++i)    		modify(target, i, needs[i]);    	vector
       
         dp(target+1,INT_MAX);    	dp[0] = 0;//什么都不买        bool lessNeed;    	for(i = 0; i <= target; i++)    	{
       		if(dp[i] == INT_MAX)    			continue;    	    vector
        
          count(n); for(j = 0; j < n; ++j) count[j] = getnum(i,j); for(j = 0; j < n; ++j) { newstate = i; num = count[j]+1;//状态i下，第j个物品的个数,再买一件+1 if(num > needs[j]) continue;//超数量了 modify(newstate, j, num); if(newstate <= target) dp[newstate] = min(dp[newstate],dp[i]+price[j]); } for(k = 0; k < special.size(); ++k) { newstate = 0; lessNeed = true; for(j = 0; j < n; ++j) { num = count[j]+special[k][j];//状态i下，第j个物品的个数+买大礼包的数量 if(num > needs[j]) { lessNeed = false; break; } modify(newstate, j, num); } if(lessNeed && newstate <= target) dp[newstate] = min(dp[newstate],dp[i]+special[k][n]); } } return dp[target]; } void modify(int& state, int i, int newnum) { int bit = 3*i, k = 0, newnum_bit; for(k = 0; k < 3; ++k,++bit) state = (~(1<
         
          >k)&1;// if(newnum_bit) state |= (1<
          
           >bit)&1); return num; }};
          
         
        
       
      
     
    
   

2.2 6维动态规划

• 把单个的也处理成大礼包，统一处理
• 不满6个的都补满，方便处理

class Solution {
   public:    int shoppingOffers(vector
   
    & price, vector
    
     
      >& special, vector
      
       & needs) {
       	int n = price.size();    	int i,j,a,b,c,d,e,f, money;    	for(i = 0; i < n; ++i)    	{
       		vector
       
         bag(7,0);    		bag[i] = 1;    		bag[6] = price[i];    		special.push_back(bag);//单个物品，加入礼包    	}    	int dp[7][7][7][7][7][7];        memset(dp,0x7f,sizeof(dp));//按字节赋值，1字节8位 0111 1111    	dp[0][0][0][0][0][0] = 0;    	vector
        
          t(6,0); while(needs.size() < 6) needs.push_back(0); for(i = 0; i < needs.size(); ++i) t[i] = needs[i]; for(vector
         
           & s : special) { vector
          
            nd(6,0); money = s.back(); for(j = 0; j < s.size()-1; ++j) nd[j] = s[j]; for(a = 0; a <= t[0]; ++a) for(b = 0; b <= t[1]; ++b) for(c = 0; c <= t[2]; ++c) for(d = 0; d <= t[3]; ++d) for(e = 0; e <= t[4]; ++e) for(f = 0; f <= t[5]; ++f) { if(dp[a][b][c][d][e][f] != 0x7f7f7f7f && a+nd[0] <= needs[0] && b+nd[1] <= needs[1] && c+nd[2] <= needs[2] && d+nd[3] <= needs[3] && e+nd[4] <= needs[4] && f+nd[5] <= needs[5]) dp[a+nd[0]][b+nd[1]][c+nd[2]][d+nd[3]][e+nd[4]][f+nd[5]] = min(dp[a+nd[0]][b+nd[1]][c+nd[2]][d+nd[3]][e+nd[4]][f+nd[5]], dp[a][b][c][d][e][f]+money); } } return dp[t[0]][t[1]][t[2]][t[3]][t[4]][t[5]]; } };
          
         
        
       
      
     
    
   

324 ms 11 MB

转载地址：https://michael.blog.csdn.net/article/details/106290676 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！