第一场（C-牛妹的春游）

链接：https://ac.nowcoder.com/acm/contest/6218/C
来源：牛客网

题目描述：
众所周知，牛妹要组织公司的出游。要准备面包和饮料。她买到的面包和饮料都是捆绑销售的，也就是说，一个大包装里面x个面包+y个饮料，花费t元。
为了满足公司的要求，需要一定数量的面包和饮料。
你的任务就是帮助牛妹计算，为了满足公司需要，一共最少花费多少钱。

示例1
输入
5,60,[[3,36,120],[10,25,129],[5,50,250],[1,45,130],[4,20,119]]
输出
249
备注:
每种大包装只能最多买一个，所需面包breadNum、饮料的总量beverageNum均不超过2000
牛妹一定能找到满足要求的方案让大家能够出游。
解题思路：
每个包装只能买一次，经典的01背包问题（容量倒序遍历）。因为购买的面包和饮料可以多于需要的数量，所以dp数组的状态转移公式需要略作修改。
代码：

class Solution {
public:
    /**
     * 
     * @param breadNum int整型 
     * @param beverageNum int整型 
     * @param packageSum int整型vector<vector<>> 每个一维数组中有三个数，依次表示这个包装里面的面包数量、饮料数量、花费
     * @return int整型
     */
    int minCost(int br, int be, vector<vector<int>>& pkg) {
        // write code here
        int dp[2005][2005];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        dp[0][0] = 0;
        for(auto& p : pkg) {
            for(int i = br; i >= 0; --i) {
                for(int j = be; j >= 0; --j) {
                    dp[i][j] = min(dp[i][j], dp[max(0, i - p[0])][max(0, j - p[1])] + p[2]);
                }
            }
        }
        return dp[br][be];
    }
};