牛妹的春游-题解

中等难度动态规划
基本就是个背包，众所周知，一维背包，下标是“容量”，dp值是“价值”
只不过变成二维了
01背包的改进而已
dp[i][j]就相当于两种“背包容量”，最终求得“背包价值最值”
即，dp[面包][饮料]是总花费，要求dp最小值

class Solution {
public:
    /**
     *
     * @param breadNum int整型
     * @param beverageNum int整型
     * @param packege int整型vector<vector<>> 每个一维数组中有三个数，依次表示这个包装里面的面包数量、饮料数量、花费
     * @return int整型
     */
    int minCost(int breadNum, int beverageNum, vector<vector<int> >& packageSum) {
        // write code here
       vector<vector<int> > dp(breadNum+1, vector<int>(beverageNum+1, 0x3f3f3f));
        dp[0][0] = 0;
        int k = packageSum.size();
        if (k == 0) return 0;
        for (int i = 0; i < k; i ++) {
            for (int j = breadNum; j >= 0; j --) {
                for (int t = beverageNum; t >= 0; t--) {
                    int j1 = j + packageSum[i][0];
                    int t1 = t + packageSum[i][1];
                    if (j1 > breadNum) j1 = breadNum;
                    if (t1 > beverageNum) t1 = beverageNum;
                    dp[j1][t1] = min (dp[j][t] + packageSum[i][2], dp[j1][t1]);
                }
            }
        }
        return dp[breadNum][beverageNum];
    }
};