LeetCode 638. 大礼包（无限背包DP）

示例 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 {
	int n;
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
    	n = price.size();
    	int i, j, k, target = 0, num, newstate;
    	for(i = 0; i < n; ++i)
    		modify(target, i, needs[i]);
    	vector<int> dp(target+1,INT_MAX);
    	dp[0] = 0;//什么都不买
        bool lessNeed;

    	for(i = 0; i <= target; i++)
    	{
    		if(dp[i] == INT_MAX)
    			continue;
    	    vector<int> 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<<bit))&(state);//清零3位组成的一个物品数量
    	bit = 3*i;
    	for(k = 0; k < 3; ++k,++bit)
    	{
    		newnum_bit = (newnum>>k)&1;//
    		if(newnum_bit)
    			state |= (1<<bit);
    	}
    }
    int getnum(int state, int i)
    {
    	int bit = 3*i+2, num = 0;
    	for(int k = 0; k < 3; ++k,--bit)
    		num = num*2+((state>>bit)&1);
    	return num;
    }
};

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
    	int n = price.size();
    	int i,j,a,b,c,d,e,f, money;
    	for(i = 0; i < n; ++i)
    	{
    		vector<int> 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<int> t(6,0);
        while(needs.size() < 6)
    		needs.push_back(0);
    	for(i = 0; i < needs.size(); ++i)
    		t[i] = needs[i];
    	for(vector<int> & s : special)
	    {
	    	vector<int> 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]];
    }	
};