A just for fun only DP solution

• 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~~

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

• 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));
``````

• 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];
}
``````

• 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.

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

• @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?

• @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.

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

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