A just for fun only DP solution


  • 8
    D

    it seems very like the dynamic programming problem. But when I solve the dp problem such like knapsack problem. I need the end of this problem, i.e. the volume of knapsack. If I know this, then the problem totally a knapsack problem. luckily, I get this from

    1. There are at most 6 kinds of items, 100 special offers.
    2. For each item, you need to buy at most 6 of them.
      Then I add to 6 item for every input argument.
      This code have O(special offers size) time complex. When the input is small, it's not the best time complex. And it also not very general.
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs)
    {
    	int n = price.size();
    	for (int i = n; i < 6; i++)
    	{
    		price.push_back(0);
    		needs.push_back(0);
    	}
    	for (int i = special.size() - 1; i >= 0; i--)  // fill special to 6 items
    	{
    		int t = special[i][n];
    		special[i][n] = 0;
    		for (int j = n + 1; j < 7; j++)
    			special[i].push_back(0);
    		special[i][6] = t;
    	}
    	int dp[7][7][7][7][7][7], m = special.size();
    	//memset(dp, INT_MAX, 7 * 7 * 7 * 7 * 7 * 7);      
    	//as @vallentin-petrov point out, memset fill the space by byte
    	for (int j = 0; j < 7; j++)
    	{
    		for (int k = 0; k < 7; k++)
    		for (int p = 0; p < 7; p++)
    		for (int q = 0; q < 7; q++)
    		for (int r = 0; r < 7; r++)
    		for (int s = 0; s < 7; s++)
    			dp[j][k][p][q][r][s]=j*price[0]+k*price[1]+p*price[2]+q*price[3]+r*price[4]+s*price[5];
    	}
    	for (int i = 0; i < m; i++)  // then it just a dynamic programming problem
    	{
    		for (int j = special[i][0]; j < 7; j++)
    		for (int k = special[i][1]; k < 7; k++)
    		for (int p = special[i][2]; p < 7; p++)
    		for (int q = special[i][3]; q < 7; q++)
    		for (int r = special[i][4]; r < 7; r++)
    		for (int s = special[i][5]; s < 7; s++)
    		{
    			int tt=dp[j-special[i][0]][k-special[i][1]][p-special[i][2]]
    				[q-special[i][3]][r-special[i][4]][s-special[i][5]];
    			if (tt != INT_MAX)
    				dp[j][k][p][q][r][s]=min(dp[j][k][p][q][r][s],tt+special[i][6]);
    		}
    	}
    	return dp[needs[0]][needs[1]][needs[2]][needs[3]][needs[4]][needs[5]];
    }
    

    special thanks to @vallentin-petrov for point out the problem about memset~~
    And thanks to @wulingyun16 for his advice~~


  • 2

    That is what I thought about the dp solution. Yea! A 6D matrix haha!


  • 0
    V

    memset does not work in this case because it fills the memory with bytes not ints. In your case it fills the memory with 0xff, which gets translated into -1 as int. You might fix it if you use unsigned int array for your dp.

    unsigned int dp[7][7][7][7][7][7], m = special.size();
    memset(dp, 0xff, 7 * 7 * 7 * 7 * 7 * 7 * sizeof(unsigned int));
    

  • 1
    C

    I have been silly as well, I did the same thing in Java

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            
            if (null == price || 0 == price.size() || null == needs || 0 == needs.size())
                return 0;
            
            int item0 = needs.get(0), 
                item1 = needs.size() >= 2? needs.get(1) : 0, 
                item2 = needs.size() >= 3? needs.get(2) : 0,
                item3 = needs.size() >= 4? needs.get(3) : 0,
                item4 = needs.size() >= 5? needs.get(4) : 0,
                item5 = needs.size() >= 6? needs.get(5) : 0;
            
            // 6 dimensional dp
            int[][][][][][] dp = new int[7][7][7][7][7][7];
            
            int price0 = price.get(0), 
                price1 = price.size() >= 2? price.get(1) : 0, 
                price2 = price.size() >= 3? price.get(2) : 0,
                price3 = price.size() >= 4? price.get(3) : 0, 
                price4 = price.size() >= 5? price.get(4) : 0, 
                price5 = price.size() >= 6? price.get(5) : 0;
                
            // fill special to length 7
            // the actual items listed in an offer
        	// *** fill special is different, as the price 2 3 5, should be 2 3 0 0 0 0 5 (the cost is 5)
            // not 2 3 5 0 0 0 0 (the cost is 0)
            if (special != null && special.size() > 0 && special.size() < 7) {
    	        for (int i = 0; i < special.size(); i ++) {
    	        	List<Integer> temp = special.get(i);
    	        	for (int j = price.size(); j < 6; j ++) temp.add(j, 0);
    	        }
            }
            
            // init dp array
            // dp[0][0][x][0][0][0], set as single price
            dp[0][0][0][0][0][0] = 0;
    
            for (int i = 0; i < 7; i ++) 
                for (int j = 0; j < 7; j ++)
                    for (int k = 0; k < 7; k ++)
                        for (int l = 0; l < 7; l ++)
                            for (int m = 0; m < 7; m ++) 
                                for (int n = 0; n < 7; n ++) {
                                    dp[i][j][k][l][m][n] = price0 * i + price1 * j + price2 * k
                                        + price3 * l + price4 * m + price5 * n; 
                                }
            
            for (List<Integer> cur: special) {
            	
                for (int i = cur.get(0); i < 7; i ++) 
                    for (int j = cur.get(1); j < 7; j ++)
                        for (int k = cur.get(2); k < 7; k ++)
                            for (int l = cur.get(3); l < 7; l ++)
                                for (int m = cur.get(4); m < 7; m ++) 
                                    for (int n = cur.get(5); n < 7; n ++) {
                                    	dp[i][j][k][l][m][n] = Math.min(dp[i][j][k][l][m][n], 
                                                dp[i - cur.get(0)][j - cur.get(1)][k - cur.get(2)][l - cur.get(3)]
                                                    [m - cur.get(4)][n - cur.get(5)] + cur.get(6));
                                    }
            }
                                    
            return dp[item0][item1][item2][item3][item4][item5];
        }
    

  • 1
    W

    This idea is awesome.
    For the 6D dp array initialization, I think you can directly use each item's price to calculate the "full price" instead of using INTMAX. Therefore, you don't have to treat every item as a special offer and push it in "special" vector.


  • 0
    D

    @vallentin.petrov Oh, thank you so much for you advice..I will try it~~Thanks (^_^)


  • 0
    D

    @wulingyun16
    I am so sorry if I miss something.
    Is this method can deal with case such as [2,5], [[3,0,5],[1,2,10]], [3,2], which need to buy some item with item's price?


  • 0
    W

    @donggua_fu
    Yes, it can. Actually @CHYGO in the 4th floor already used this method to initialize dp array.

    From this initialization method, we directly have dp[0][2][0][0][0][0] = 25 = 10, dp[2][0][0][0][0][0] = 22 = 4, and dp[3][2][0][0][0][0] = 32 + 25 = 16.

    Therefore, the results dp[3][2] = min(dp[3][2] = 16, dp[0][2] + special[0] = 15, dp[2][0]+special[1] = 14) = 14.


  • 0
    D

    @wulingyun16 OH, I now get the key point. Thanks a lot for your patient. (^_^)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.