在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
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和2B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。

说明:

1. 最多6种物品， 100种大礼包。
2. 每种物品，你最多只需要购买6个。
3. 你不可以购买超出待购清单的物品，即使更便宜。

算法分析：

        本题采用动态规划法，难点在于构造备忘录，如果用数组的话，维数太大，操作起来比较麻烦，网上大佬的方法是，将needs数组的每一位连接起来构成一个10进制数，例如题中给的第一个例子，needs数组为3,2，那么就定义一个need=32，用来代替needs数组，然后用一个map结构来储存已经求到的子问题的解。本题的递归关系比较简单，首先要用单价来求不同needs对应的花费的初始值，定义一个数组temp来储存选了一个礼包后needs数组的变化，即temp=needs-special[i]，在减的过程中如果出现小于0的值即表示购买当前礼包后超过了代购清单，就退出。然后自顶向下的求出解。代码如下：

class Solution {
public:
unordered_map <int,int> map;
//保存子问题的解
int getkey(vector<int> needs)
//将needs数组转化为一个十进制数
{
int res=0;
int len=needs.size();
for(int i=len-1;i>=0;i--)
res+=(int)(needs[i]*pow((double)10,len-1-i));
return res;
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs)
{
int m=price.size();
int n=special.size();
int need=getkey(needs);
if(map[need])
//如果已经求过了当前needs的最低花费则直接返回结果。
return map[need];
int minpay=0;
for(int i=0;i<m;i++)
minpay+=rpice[i]*needs[i];//将每件物品都按单价购买的花费作为初始值。
vector<int> temp;
for(int i=0;i<n;i++)//对于当前needs，求对于每个礼包购买与否的情况
{
int j;
temp=needs;
for(j=0;j<m;j++)
{
temp[j]=needs[j]-special[i][j];
//保存购买当前礼包后得新needs数组
if(temp[j]<0)
break;
}
if(j==m)
minpay=min(minpay,special[i][j]+shoppingOffers(price,special,temp));//向下递推
}
map[key]=minpay;//保存求得的当前needs的最小消费
return minpay;
}
};

最后

以上就是虚幻蜻蜓为你收集整理的LeetCode_638（动态规划）算法分析：的全部内容，希望文章能够帮你解决LeetCode_638（动态规划）算法分析：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。