一、零钱兑换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;;
}