牛妹的春游-题解
中等难度动态规划
基本就是个背包,众所周知,一维背包,下标是“容量”,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]; } };