一、零钱兑换I
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
实例2：
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
思路：
动态规划的问题，dp[i] = min(cur_min, dp[i - coins[j]])，如果dp[i - coins[j]]存在，那么在这个基础上增加1一个硬币，与当前记录的最小值进行比较，如果小于则进行修改；
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount == 0 && !coins.size()) return -1;
int *dp = new int[amount + 1];
for(int i = 0; i <= amount; ++i)
dp[i] = -1;
dp[0] = 0;
for(int i = 1; i <= amount; ++i) {
int _min = INT_MAX;
for(int j = 0; j < coins.size(); ++j) {
int temp = i - coins[j];
if(temp >= 0 && dp[temp] != -1) {
_min = min(_min, dp[temp] + 1);
}
}
dp[i] = _min == INT_MAX ? -1 : _min;
}
return dp[amount];
}
};
暴力方式（但是超出时间限制 ）
class Solution {
public:
int min;
int coinChange(vector<int>& coins, int amount) {
min = -1;
if(amount == 0 && !coins.size()) return -1;
func1(coins, amount, 0);
return min;
}
void func1(vector<int> &coins, int amount, int k) {
if (amount == 0) {
if(min == -1 || min > k) {
min = k;
}
return;
}
if (amount < 0) return;
for (int i = 0; i < coins.size(); ++i) {
if(k + 1 < min || min == -1)
func1(coins, amount - coins[i], k + 1);
else
return;
}
}
};
二、零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
分析：
amount = 5, coins = [1, 2, 5]
| amount\coins | 1 | 2 | 5 |
|---|---|---|---|
| 1 | (1) | ||
| 2 | (1 1) | (2) _____ 2 - 2 = 0 | |
| 3 | (1 1 1) | (2 1) _____ 3 - 2 = 1 -->(1) | |
| 4 | (1 1 1 1) | (2 2) (2 1 1) _____ 4 - 2 = 2 --> (2) (1 1) | |
| 5 | (1 1 1 1 1) | (2 2 1) (2 1 1 1) _____ 5 - 2 = 3 -- > (2 1) (1 1 1) | (5) |
可以看出用一个个不同面值的coin去组成amount，全部相加起来的可能性为结果，比如此处amount = 5的所有可能性为 dp[5] = 1 + 2 + 1 = 4
代码：
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(coins.size() == 0 && amount != 0) return 0;
int *dp = new int[amount + 1];
// 初始化
dp[0] = 1;
for(int i = 1; i <= amount; ++i) dp[i] = 0;
for(int i = 0; i < coins.size(); ++i) {
for(int j = 1; j <= amount; ++j) {
int temp = j - coins[i];
if(temp >= 0) {
dp[j] += dp[temp];
}
}
}
return dp[amount];
}
};
注意：易错点
如果我们将代码写成如下，将amount放到循环的外面一层
class Solution {
public:
int change(int amount, vector<int>& coins) {
if(coins.size() == 0 && amount != 0) return 0;
int *dp = new int[amount + 1];
dp[0] = 1;
for(int i = 0; i <= amount; ++i) {
dp[i] = 0;
for(int j = 0; j < coins.size(); ++j) {
int temp = i - coins[j];
if(temp >= 0) {
dp[i] += dp[temp];
}
}
}
return dp[amount];
}
};
思考一下会出现什么结果？
when amount = 1; re = (1);
when amount = 2; re = (1 1) (2);
when amount = 3;
{
re --> when j = 0; coins[0] = 1; dp[3] += dp[2]; --> 1 + (2) (1 1) = (1 2) (1 1 1)
re --> when j = 1; coins[1] = 2; dp[3] += dp[1]; --> 2 + (1) = (2 1)
// 存在重复的(1 2) 和 (2 1)
}
如果我们把硬币面值的循环放在外面，依次放入（1）、（1，2）、（1，2，5）面值大小的硬币，在3计算与1相关的时候就不会存在 [1 ,2 ] 这种情况，在使用面值为（1，2）的时候才会出现[2，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
解释:
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和1B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。
说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。
暴力+裁枝
思路分析：
(1)直接回溯法+剪枝。对于当前需求，我们首先考虑单独购买，更新此时的最小总价。
(2)然后再去寻找是否能够购买礼包，达到降低总价的目的。那么剪枝就放在购买大礼包是否超过已经搜索到的最小值。
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int _min = 0;
// 全部商品单独买所需要的钱
for(int i = 0; i < price.size(); ++i) {
_min += needs[i] * price[i];
}
for(int i = 0; i < special.size(); ++i) {
bool ok = true;
// 判断是否满足购买礼包
for(int j = 0; j < needs.size(); ++j) {
if(needs[j] - special[i][j] < 0) {
ok = false;
break;
}
}
if(ok) {
vector<int> needs_temp;
for(int j = 0; j < needs.size(); ++j)
needs_temp.push_back(needs[j] - special[i][j]);
int money = shoppingOffers(price, special, needs_temp);
_min = min(_min, money + special[i].back());
}
}
return _min;
}
};
四、背包问题
问题基础：有N件物品和一个容量为C的背包。第i件物品的体积是W[i]，价值是V[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
怎样才能得到放入书包物品的的最大价值呢？
// 背包问题
// value表示每一个物品的价值，volume表示每一个物品的体积，max_vol表示一个包最大的体积
int package(const vector<int>& value, const vector<int>& volume, const int max_vol)
{
int* dp = new int[max_vol + 1];
dp[0] = 0;
for (int i = 1; i <= max_vol; ++i) {
dp[i] = 0;
for (int j = 0; j < volume.size(); ++j) {
if (i - volume[j] >= 0) {
dp[i] = max(dp[i], dp[i - volume[j]] + value[j]);
}
}
}
return dp[max_vol];
}
// for test code
void main() {
int P[] = { 5,8 };
int V[] = { 5,7 };
int T = 10;
vector<int> _value(P, P + 2);
vector<int> _volume(V, V + 2);
cout << package(_value, _volume, T) << endl;;
}
