admin 管理员组文章数量: 887021
大礼包
问题描述 :
在商店中， 有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
示例 1:
输入: [2,5], [3,2], [[3,0,5],[1,2,10]]
输出: 14
解释:
有A和B两种物品，价格分别为¥2和¥5。
你需要购买3个A和2个B。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。
示例 2:
输入: [2,3,4], [1,2,1], [[1,1,0,4],[2,2,1,9]]
输出: 11
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你需要买1A，2B和1C
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
可使用以下main函数：
int main(){vector<int> price;vector<vector<int>> special;vector<int> needs;int n,m;cin>>n;int p,need;for(int i=0; i<n; i++){cin>>p;price.push_back(p);}for(int i=0; i<n; i++){cin>>need;needs.push_back(need);}cin>>m;for(int i=0; i<m; i++){vector<int> oneSpecial;int qty;for(int j=0; j<n; j++){cin>>qty;oneSpecial.push_back(qty);}int amount;cin>>amount;oneSpecial.push_back(amount);special.push_back(oneSpecial);}int res=shoppingOffers(price, special, needs);cout<<res<<endl;return 0;
}
输入说明 :
首先输入物品的种类数n
下一行输入n个整数，表示物品的价格
第三行输入n个整数，表示每种物品需要购买的个数
第四行输入大礼包的种类数m，
下面m行，每一行输入一种大礼包的信息，其中，前n个整数表示该大礼包包含每种物品的数量，第n+1个整数表示大礼包的价格。
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
输出说明 :
输出结果
输入范例 :
3
2 3 4
1 2 1
2
1 1 0 4
2 2 1 9
输出范例 :
11
void dfs(vector<int> &price,vector<vector<int>> &special,vector<int> &needs,vector<int> &maxPrice,int &val,int i){int tag=0;for(int k=0;k<needs.size();k++){if(needs[k]!=0){tag=1;break;}}if(tag==0){maxPrice.push_back(val);}for(int j=i;j<special.size();j++){int flag=0;for(int k=0;k<needs.size();k++){if(needs[k]<special[j][k]){flag=1;break;}}if(flag==0){for(int k=0;k<needs.size();k++){needs[k]-=special[j][k];}val+=special[j][special[j].size()-1];}else if(flag==1){continue;}dfs(price,special,needs,maxPrice,val,j);for(int k=0;k<needs.size();k++){needs[k]+=special[j][k];}val-=special[j][special[j].size()-1];}
}int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
vector<int> maxPrice;int pprice=0;int val=0;for(int i=0;i<price.size();i++){//假设每个礼包都用不了 只能够零买 pprice+=price[i]*needs[i];}for(int i=0;i<price.size();i++){//把每一个商品都当做一个礼包放入special vector<int> tmp;for(int j=0;j<price.size();j++){if(i==j){tmp.push_back(1);}else{tmp.push_back(0);}}tmp.push_back(price[i]);special.push_back(tmp);tmp.clear();}maxPrice.push_back(pprice);dfs(price,special,needs,maxPrice,val,0);sort(maxPrice.begin(),maxPrice.end());return maxPrice[0];}
本文标签： 大礼包
版权声明：本文标题：大礼包 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687900076h155108.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论