• 
• 
  
• 上式k表示第k个捆绑物品，表示对于物品A容量减到负数了，就从0转移，即使拿了更大的容量也不会数组越界，转移也是正确的；
• 同样的表示对于物品B容量减到负数了，就从0转移，即使拿了更大的容量也不会数组越界，转移也是正确的；

class Solution {
public:
    /**
     * 
     * @param breadNum int整型 
     * @param beverageNum int整型 
     * @param packageSum int整型vector<vector<>> 每个一维数组中有三个数，依次表示这个包装里面的面包数量、饮料数量、花费
     * @return int整型
     */
    int minCost(int breadNum, int beverageNum, vector<vector<int> >& packageSum) {
        // write code here
        int n=packageSum.size();
        vector< vector < vector<int> > > dp(n+1,vector< vector<int> >(breadNum+1,vector<int>(beverageNum+1,2e9 + 7)));
        dp[0][0][0]=0;//初始化取第0个包装,0个A，0个B的最小花费为0
        for(int k=1;k<=n;k++)
        {
            int x=packageSum[k-1][0];
            int y=packageSum[k-1][1];
            int z=packageSum[k-1][2];
            for(int i=0;i<=breadNum;i++)
            {
                
                for(int j=0;j<=beverageNum;j++)
                {
                      dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][max(i-x,0)][max(j-y,0)]+z);
                      //表示可选物品为1-k,物品A容量为i,物品B容量为j的最优值（钱最少）
                }
                  
            }
        }
        return dp[n][breadNum][beverageNum];
    }
};

• 时间复杂度：存在三层循环，总的时间复杂度为$O(n*breadNum*beverageNum)$，其中$n$表示所给的数对的个数
• 空间复杂度：需要借助于一个二维数组存储最小费用，需要额外的空间为$O(n*breadNum*beverageNum)$

方法二

思路分析

核心代码

class Solution {
public:
    /**
     * 
     * @param breadNum int整型 
     * @param beverageNum int整型 
     * @param packageSum 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,2e9 + 7));//定义二维数组dp[i][j]表示i个A，j个B的最小花费
        dp[0][0]=0;//初始化0个A，0个B的最小花费为0
        int n=packageSum.size();
        for(int k=0;k<n;k++)
        {
            int x=packageSum[k][0];
            int y=packageSum[k][1];
            int z=packageSum[k][2];
            for(int i=breadNum;i>=0;i--)
            {
                for(int j=beverageNum;j>=0;j--)
                    dp[i][j] = min(dp[i][j], dp[max(i-x,0)][max(j-y,0)]+z);
                //当前捆绑套餐内A或者B大于需要的数量，那么当前剩余需求为0
            }
        }
        return dp[breadNum][beverageNum];
    }
};