公司网站建设及安全解决方案,关键词密度查询站长工具,深圳宝安区是富人区吗,商务网站建设论文总结1. 题目
在LeetCode商店中#xff0c; 有许多在售的物品。
然而#xff0c;也有一些大礼包#xff0c;每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格#xff0c;每个大礼包包含物品的清单#xff0c;以及待购物品清单。请输出确切完成待购清单的最低…1. 题目
在LeetCode商店中 有许多在售的物品。
然而也有一些大礼包每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格每个大礼包包含物品的清单以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述最后一个数字代表大礼包的价格其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
示例 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
解释:
ABC的价格分别为¥2¥3¥4.
你可以用¥4购买1A和1B也可以用¥9购买2A2B和1C。
你需要买1A2B和1C所以你付了¥4买了1A和1B大礼包1以及¥3购买1B ¥4购买1C。
你不可以购买超出待购清单的物品尽管购买大礼包2更加便宜。说明:
最多6种物品 100种大礼包。
每种物品你最多只需要购买6个。
你不可以购买超出待购清单的物品即使更便宜。来源力扣LeetCode 链接https://leetcode-cn.com/problems/shopping-offers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 状态压缩超时解
思路是把int看做买东西的个数的状态3个位最大是7题目说不超过6物品也不超过6最多18位就可以了一个int就可以存下买的物品的个数最后一个例子超时可能这个最大的状态数太大了
class Solution {int n;
public:int shoppingOffers(vectorint price, vectorvectorint special, vectorint needs) {n price.size();int i, j, k, target 0, num, newstate;for(i 0; i n; i)modify(target, i, needs[i]);vectorint dp(target1,INT_MAX);dp[0] 0;//什么都不买bool lessNeed;for(i 0; i target; i){if(dp[i] INT_MAX)continue;vectorint 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个物品的个数,再买一件1if(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 (~(1bit))(state);//清零3位组成的一个物品数量bit 3*i;for(k 0; k 3; k,bit){newnum_bit (newnumk)1;//if(newnum_bit)state | (1bit);}}int getnum(int state, int i){int bit 3*i2, num 0;for(int k 0; k 3; k,--bit)num num*2((statebit)1);return num;}
};2.2 6维动态规划
把单个的也处理成大礼包统一处理不满6个的都补满方便处理
class Solution {
public:int shoppingOffers(vectorint price, vectorvectorint special, vectorint needs) {int n price.size();int i,j,a,b,c,d,e,f, money;for(i 0; i n; i){vectorint bag(7,0);bag[i] 1;bag[6] price[i];special.push_back(bag);//单个物品加入礼包}int dp[11][11][11][11][11][11];memset(dp,0x7f,sizeof(dp));//按字节赋值1字节8位 0111 1111dp[0][0][0][0][0][0] 0;vectorint t(6,0);while(needs.size() 6)needs.push_back(0);for(i 0; i needs.size(); i)t[i] needs[i];for(vectorint s : special){vectorint 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 and[0] needs[0] bnd[1] needs[1] cnd[2] needs[2] dnd[3] needs[3] end[4] needs[4] fnd[5] needs[5])dp[and[0]][bnd[1]][cnd[2]][dnd[3]][end[4]][fnd[5]] min(dp[and[0]][bnd[1]][cnd[2]][dnd[3]][end[4]][fnd[5]],dp[a][b][c][d][e][f]money);}}return dp[t[0]][t[1]][t[2]][t[3]][t[4]][t[5]];}
};280 ms 18.4 MB C
