y总的8进制状态压缩+完全背包太难想了,这题DFS爆搜+剪枝也能过
class Solution {
public:
int ans = INT_MAX, n;
int getPrice(vector<int> &arr, vector<int>& price){
int sum = 0;
for (int i = 0; i<n; i++) sum += price[i] * arr[i];
return sum;
}
void dfs(vector<int> remain, int sum, vector<vector<int>>& offer, vector<int>& price){
//最优化剪枝
if (sum >= ans) return;
ans = min(ans, getPrice(remain, price) + sum);
for (auto &e : offer){
auto tmp = remain;
bool flag =true;
for (int i = 0; i<n; i++){
tmp[i] -= e[i];
if (tmp[i] < 0){
flag = false;
break;
}
}
if (flag)
dfs(tmp, sum + e[n], offer, price);
}
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& offer, vector<int>& needs) {
n= price.size();
vector<vector<int>> special;
//排除不划算或不合理的offer
for (auto &e: offer){
int sum = 0;
bool flag = true;
for (int i = 0; i<n; i++){
sum += e[i]*price[i];
if (e[i] > needs[i]){
flag =false;
break;
}
}
if (sum <= e[n]) flag = false;
if (flag) special.push_back(e);
}
dfs(needs, 0, special, price);
return ans;
}
};