https://leetcode.com/problems/shopping-offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
https://www.cnblogs.com/grandyang/p/7261663.html
这道题说有一些商品，各自有不同的价格，然后给我们了一些优惠券，可以在优惠的价格买各种商品若干个，要求我们每个商品要买特定的个数，问我们使用优惠券能少花多少钱，注意优惠券可以重复使用，而且商品不能多买。那么我们可以先求出不使用任何商品需要花的钱数作为结果res的初始值，然后我们遍历每一个coupon，定义一个变量isValid表示当前coupon可以使用，然后遍历每一个商品，如果某个商品需要的个数小于coupon中提供的个数，说明当前coupon不可用，isValid标记为false。如果遍历完了发现isValid还为true的话，表明该coupon可用，我们可以更新结果res，对剩余的needs调用递归并且加上使用该coupon需要付的钱数。最后别忘了恢复needs的状态
https://leetcode.com/articles/shopping-offers/
https://discuss.leetcode.com/topic/95200/simple-java-recursive-solution/
https://leetcode.com/articles/shopping-offers/
X.
X. DP
https://leetcode.com/problems/shopping-offers/discuss/105214/A-just-for-fun-only-DP-solution
https://www.acwing.com/solution/leetcode/content/493/
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
https://www.cnblogs.com/grandyang/p/7261663.html
这道题说有一些商品，各自有不同的价格，然后给我们了一些优惠券，可以在优惠的价格买各种商品若干个，要求我们每个商品要买特定的个数，问我们使用优惠券能少花多少钱，注意优惠券可以重复使用，而且商品不能多买。那么我们可以先求出不使用任何商品需要花的钱数作为结果res的初始值，然后我们遍历每一个coupon，定义一个变量isValid表示当前coupon可以使用，然后遍历每一个商品，如果某个商品需要的个数小于coupon中提供的个数，说明当前coupon不可用，isValid标记为false。如果遍历完了发现isValid还为true的话，表明该coupon可用，我们可以更新结果res，对剩余的needs调用递归并且加上使用该coupon需要付的钱数。最后别忘了恢复needs的状态
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { int res = 0, n = price.size(); for (int i = 0; i < n; ++i) { res += price[i] * needs[i]; } for (auto offer : special) { bool isValid = true; for (int j = 0; j < n; ++j) { if (needs[j] - offer[j] < 0) isValid = false; needs[j] -= offer[j]; } if (isValid) { res = min(res, shoppingOffers(price, special, needs) + offer.back()); } for (int j = 0; j < n; ++j) { needs[j] += offer[j]; } } return res; }
答案拿什么当做subproblem？ 拿套餐的范围作为subproblem。
也就是最基本的版本，1. 没有特别套餐的话， 只能单价买产品，这种情况的价格就是最初级的subproblem的解。
2. 如果有特别套餐1的话。 这个套餐会不会被使用。
3. 如果有特别套餐2的话， 会不会被使用。
。。。
用的是recursion+DP。 这里的DP 没有用array 之类的，也是非常不按套路
为什么是recursion？ 因为最终答案是：没有套餐的情况和 至少有第1个套餐option套餐的情况下的最好情况做比较出来的。 至少有第1个套餐option套餐是由 至少有第1个套餐option套餐 和至少有2个套餐的情况比较出来的。。。 所以要一路算到后面
也就是最基本的版本，1. 没有特别套餐的话， 只能单价买产品，这种情况的价格就是最初级的subproblem的解。
2. 如果有特别套餐1的话。 这个套餐会不会被使用。
3. 如果有特别套餐2的话， 会不会被使用。
。。。
用的是recursion+DP。 这里的DP 没有用array 之类的，也是非常不按套路
为什么是recursion？ 因为最终答案是：没有套餐的情况和 至少有第1个套餐option套餐的情况下的最好情况做比较出来的。 至少有第1个套餐option套餐是由 至少有第1个套餐option套餐 和至少有2个套餐的情况比较出来的。。。 所以要一路算到后面
就是你不可以购买超出待购清单的物品，即使更便宜，这个很重要，可以进行减枝，加快计算。
在这里使用记忆化搜索(Search Memoization)方法。
（1）令 dp[cur] = val，表示，在我们需要的商品数量为cur时，的最小花费为val。例如dp[(1,2,1)] = val，表示我们需要的商品数cur = [1,2,1] 时的最小花费为val，其中dp可以使用字典数据类型。
（2）从上向下，进行递归，如下草图（黑色线表示下递归，红色虚线表示回溯底层最优解），在最原始的状态上，遍历每一个礼包，获取最优值，每个礼包继续下递归，完成深度优先搜索。在这个过程中，每次遍历的初始化状态就是，不使用礼包时的价格。所以递推方程为：
dp[cur] = min(val, dp.get(tmp, dfs(tmp)) + spec[-1])
tmp为cur使用了某一个礼包之后的需要数， spec[-1] 对应这当前礼包的价格。在同一层上遍历一边，获取最小的那个值。
def shoppingOffers(self, price, special, needs):
dp = {} # 初始化，dp,用于保存每个状态的最优解
def dfs(cur):
val = sum(cur[i] * price[i] for i in range(len(needs))) # 不用礼包时的价格
for spec in special:
tmp = [cur[j] - spec[j] for j in range(len(needs))]
if min(tmp) >= 0: # 过滤掉，礼包里面的商品多于需求的，礼包， 其中这个一步也相当于减枝
val = min(val, dp.get(tuple(tmp), dfs(tmp)) + spec[-1]) # 循环--递归--获取最优解
dp[tuple(cur)] = val
return val
return dfs(needs)
（2）记忆化搜索(Search Memoization)
算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的[1]。
https://discuss.leetcode.com/topic/95200/simple-java-recursive-solution/
The basic idea is to pick each offer, and subtract the needs. And then compute the price without the offer.
Pick whichever is minimum.
Pick whichever is minimum.
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int result = Integer.MAX_VALUE;
//apply each offer to the needs, and recurse
for(int i = 0; i < special.size(); i++) {
List<Integer> offer = special.get(i);
boolean invalidOffer = false;
int offerCount = Integer.MAX_VALUE; // number of times offer can be applied
for(int j = 0; j < needs.size(); j++) { // pre-compute number of times offer can be called
int remain = needs.get(j) - offer.get(j);
if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
if(offer.get(j) > 0)
offerCount = Math.min(offerCount, needs.get(j)/offer.get(j));
}
for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
int remain = needs.get(j) - offer.get(j) * offerCount;
needs.set(j, remain);
}
if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
result = Math.min(result, shoppingOffers(price, special, needs) + (offerCount * offer.get(needs.size())));
}
for(int j = 0; j < needs.size(); j++) { // reset the needs
int remain = needs.get(j) + offer.get(j) * offerCount;
needs.set(j, remain);
}
}
// choose b/w offer and non offer
int nonOfferPrice = 0;
for(int i = 0; i < needs.size(); i++) {
nonOfferPrice += price.get(i) * needs.get(i);
}
return Math.min(result, nonOfferPrice);
}
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
return shopping(price, special, needs);
}
public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int j = 0, res = dot(needs, price);
for (List<Integer> s : special) {
ArrayList<Integer> clone = new ArrayList<>(needs);
for (j = 0; j < needs.size(); j++) {
int diff = clone.get(j) - s.get(j);
if (diff < 0)
break;
clone.set(j, diff);
}
if (j == needs.size())
res = Math.min(res, s.get(j) + shopping(price, special, clone));
}
return res;
}
public int dot(List<Integer> a, List<Integer> b) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i) * b.get(i);
}
return sum;
}
X. DFS+Cache
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
Map<List<Integer>, Integer> map = new HashMap();
return shopping(price, special, needs, map);
}
public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs,
Map<List<Integer>, Integer> map) {
if (map.containsKey(needs))
return map.get(needs);
int j = 0, res = dot(needs, price);
for (List<Integer> s : special) {
ArrayList<Integer> clone = new ArrayList<>(needs);
for (j = 0; j < needs.size(); j++) {
int diff = clone.get(j) - s.get(j);
if (diff < 0)
break;
clone.set(j, diff);
}
if (j == needs.size())
res = Math.min(res, s.get(j) + shopping(price, special, clone, map));
}
map.put(needs, res);
return res;
}
public int dot(List<Integer> a, List<Integer> b) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i) * b.get(i);
}
return sum;
}
https://discuss.leetcode.com/topic/95237/java-dfs-dp public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
Map<List<Integer>, Integer> dp = new HashMap<>();
List<Integer> allZero = new ArrayList<>();
for(int i=0;i<needs.size();i++) {
allZero.add(0);
}
dp.put(allZero, 0);
return dfs(needs, price, special, dp);
}
private int dfs(List<Integer> needs, List<Integer> price, List<List<Integer>> special, Map<List<Integer>, Integer> dp) {
if(dp.containsKey(needs)) return dp.get(needs);
int res = Integer.MAX_VALUE;
for(List<Integer> s : special) {
List<Integer> needsCopy = new ArrayList<>(needs);
boolean valid = true;
for(int i=0;i<needs.size();i++) {
needsCopy.set(i, needsCopy.get(i) - s.get(i));
if(needsCopy.get(i) < 0) {
valid = false;
break;
}
}
if(valid) {
res = Math.min(res, s.get(needs.size()) + dfs(needsCopy, price, special, dp));
}
}
//What if we do not use specials? specials can be deceiving,
//perhaps buying using regular prices is cheaper.
int noSpecial = 0;
for(int i=0;i<needs.size();i++) {
noSpecial += needs.get(i) * price.get(i);
}
res = Math.min(res, noSpecial);
dp.put(needs, res);
return res;
}
}X.
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { int res = inner_product(price.begin(), price.end(), needs.begin(), 0); for (auto offer : special) { vector<int> r = helper(offer, needs); if (r.empty()) continue; res = min(res, shoppingOffers(price, special, r) + offer.back()); } return res; } vector<int> helper(vector<int>& offer, vector<int>& needs) { vector<int> r(needs.size(), 0); for (int i = 0; i < needs.size(); ++i) { if (offer[i] > needs[i]) return {}; r[i] = needs[i] - offer[i]; } return r; }
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int n = price.size();
int result = std::inner_product(price.begin(), price.end(), needs.begin(), 0);
for (auto& offer : special) {
vector<int> r = specialAttempt(offer, needs, n);
if (r.empty()) continue;
int expense = offer.back() + shoppingOffers(price, special, r);
result = std::min(result, expense);
}
return result;
}
private:
vector<int> specialAttempt(const vector<int>& offer, const vector<int>& needs, int n) {
vector<int> result(n, 0);
for (int i = 0; i < n; ++i) {
int delta = needs[i] - offer[i];
if (delta < 0) return {};
result[i] = delta;
}
return result;
}
https://leetcode.com/problems/shopping-offers/discuss/105214/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
- There are at most 6 kinds of items, 100 special offers.
- 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.
A more concise way to use DP is to store the number of items as a number in base 7(it costs more time). Thus we don't need a 6D array and so much for loops. For example, if the number of items are
[2,3,1], we will store it in f[i], i = 2*1 + 3*7^1 + 1*7^2. public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int[] sp = new int[special.size()];
for (int j = 0; j < special.size(); j++) {
List<Integer> spe = special.get(j);
int p = 1;
int sum = 0;
for (int t = 0; t < spe.size() - 1; t++) {
sum += p * spe.get(t);
p *= 7;
}
sp[j] = sum;
}
int target = 0, k = 1;
for (int i = 0; i < price.size(); i++) {
target += k * needs.get(i);
k *= 7;
}
int[] f = new int[target + 1];
Arrays.fill(f, Integer.MAX_VALUE);
f[0] = 0;
for (int i = 1; i <= target; i++) {
if (!valid(i, target)) {
continue;
}
k = 1;
int res = f[i];
for (int j = 0; j < price.size(); j++) {
if (i - k >= 0 && (f[i - k] != Integer.MAX_VALUE && f[i - k] + price.get(j) < res) && valid(i - k, i)) {
res = f[i - k] + price.get(j);
}
k *= 7;
}
for (int j = 0; j < special.size(); j++) {
List<Integer> spe = special.get(j);
int sum = sp[j];
if (i >= sum && (f[i - sum] != Integer.MAX_VALUE && f[i - sum] + spe.get(spe.size() - 1) < res) && valid(i - sum, i)) {
res = f[i - sum] + spe.get(spe.size() - 1);
}
}
f[i] = res;
}
return f[target];
}
public boolean valid(int n, int j) {
List<Integer> l = new ArrayList<>();
while (n != 0 && j != 0) {
if (n % 7 > j % 7) {
return false;
}
n /= 7;
j /= 7;
}
return true;
}
https://www.acwing.com/solution/leetcode/content/493/
(动态规划) O(n7(n+m))O(n7(n+m))
类似于完全背包问题，设计状态 f(i0,i1,i2,i3,i4,i5)f(i0,i1,i2,i3,i4,i5) 表示购买了 i0i0 个 A，i1i1 个 B，……，i5i5 个 F 的最少花费。
初始状态 f(0,0,0,0,0,0)=0f(0,0,0,0,0,0)=0，其余为正无穷。
转移时，可以每次单独买一个。例如单独买一个 A，则 f(i0,i1,i2,i3,i4,i5)=min(f(i0,i1,i2,i3,i4,i5),f(i0−1,i1,i2,i3,i4,i5)+price[0])f(i0,i1,i2,i3,i4,i5)=min(f(i0,i1,i2,i3,i4,i5),f(i0−1,i1,i2,i3,i4,i5)+price[0])；也可以从大礼包转移，转移类似。
最终 f(needs[0],needs[1],needs[2],needs[3],needs[4],needs[5])f(needs[0],needs[1],needs[2],needs[3],needs[4],needs[5]) 为答案。
时间复杂度
状态数为 O(n7)O(n7)，其中 nn 为物品个数，单独price的转移需要 O(n)O(n)，大礼包转移需要 O(m)O(m)，故总时间复杂度为 O(n7(n+m))O(n7(n+m))。
实现细节
为了防止数组维数过大，if 语句过多，在实现时对状态进行压缩。由于最多只可能买 6 个，可以使用 7 进制进行状态表示。但由于计算机采用二进制，所以考虑八进制压缩更加合理。
将不足 6 个物品的情况补齐，方便代码编写。
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int n = price.size(), m = special.size();
vector<int> f(270000, INT_MAX);
f[0] = 0;
for (int i = n; i < 6; i++) {
price.push_back(0);
needs.push_back(0);
}
for (int i = 0; i < m; i++) {
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 T = 0;
// T 表示最终的状态。
for (int i = 0; i < 6; i++)
T |= needs[i] << (i * 3);
for (int S = 1; S <= T; S++) {
bool check_flag = true;
for (int i = 0; i < 6; i++) {
int s = (S >> (i * 3)) & 7;
// 小 s 就代表大 S 中的某三个二进制位，相当于 i0, i1, ..., i5。
if (s > needs[i]) {
check_flag = false;
break;
}
}
if (!check_flag)
continue;
for (int i = 0; i < 6; i++) {
int s = (S >> (i * 3)) & 7;
if (s > 0)
f[S] = min(f[S], f[(S & (~(7 << (i * 3)))) | ((s - 1) << (i * 3))] + price[i]);
}
for (int i = 0; i < m; i++) {
check_flag = true;
int t = 0;
for (int j = 0; j < 6; j++) {
int s = S >> (j * 3) & 7;
if (s < special[i][j]) {
check_flag = false;
break;
}
t |= (s - special[i][j]) << (j * 3);
}
if (check_flag)
f[S] = min(f[S], f[t] + special[i][6]);
}
}
return f[T];
}
