牛妹的春游

[编程题]牛妹的春游

热度指数：605 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出两个正整数x，y，另给出若干个数对[ai,bi,ci]，请挑选若干数对使得挑出的数对ai的和不小于x，bi的和不小于y，计算挑出数对的ci的和的最小值

注：

每个数对只能挑选一次，x和y均小于2000

示例1

输入

5,60,[[3,36,120],[10,25,129],[5,50,250],[1,45,130],[4,20,119]]

输出

说明

挑选第一和第二个数对

备注:

每种大包装只能最多买一个，所需面包breadNum、饮料的总量beverageNum均不超过2000
牛妹一定能找到满足要求的方案让大家能够出游。

算法知识视频讲解

C/C++

抓紧进攻

看到以后首先想用DFS解决，写了如下代码：

class Solution {
public:
    int min = 99999;
    int mybreadNum = 0;
    int mybeverageNum = 0;
    int size;
    int minCost(int breadNum, int beverageNum, vector<vector<int> >& packageSum) {
        // write code here
        mybreadNum = breadNum;
        mybeverageNum = beverageNum;
        size = packageSum.size();
        DFS(0,0,0,0,packageSum);
        return min;
    }
    void DFS(int index,int currentx,int currenty,int currentt,vector<vector<int> >& mypackageSum)
    {
        if(index==size)
        {
            return;
        }
        if(mypackageSum[index][0] + currentx > mybreadNum)
        {
            if(mypackageSum[index][1] + currenty > mybeverageNum)
            {
                if(mypackageSum[index][2] + currentt < min)
                {
                    min = mypackageSum[index][2] + currentt;
                }
            }
        }
        DFS(index+1,currentx,currenty,currentt,mypackageSum);
        if(currentt + mypackageSum[index][2] < min)
        {
            DFS(index+1,currentx+mypackageSum[index][0],mypackageSum[index][1] + currenty,
                mypackageSum[index][2] + currentt,mypackageSum);
        }
    }
}；

调试之后发现只能通过10%的用例，可能是DFS本身脱离不了回溯枚举的性质，时空开销太高。。。

于是仔细查了一下大佬们的写法，发现主要有如下关键点：

1.实际相当于动态规划二维背包问题，需要利用滚动数组进行空间优化（三维降二维，注意倒序枚举，dp[i][j]存储的是当需要i个面包和j个饮料时的最小所需钱数）。

2.DP本身每次记录的是局部最优，使用DP时要确定两大要素：

（1）边界。本题的边界是dp[i][j]=0，即不需要面包和饮料时不花钱。

（2）状态转移方程。如果不顾空间开销，那么实际的状态转移方程就需要开三维数组，即记录对于当前第k个捆绑套餐，当需要i个面包和j个饮料时所需的最小金额dp[k][i][j]；

进行滚动数组优化后，用当前的位置存储上一个捆绑套餐所需的最小金额，即实现降维，得到的状态转移方程为：

dp[i][j] = min( dp[i][j] , dp[ max(i-packageSum[k][0],0) ][ max(j-packageSum[k][1],0) ] + packageSum[k][2] );

在这里，max(i-packageSum[k][0],0)和max(j-packageSum[k][1],0)的意思是，只要当前捆绑套餐内带有的面包数或饮料数大于所需数量，那么就视为完成对于面包或饮料的需求，即达到当前剩余需求为0。

3.DP在背包问题中本身也是一种枚举策略，但是每次枚举的都是局部最优，且最终必然有全局最优。因此对于本题，需要枚举各个捆绑套餐。加上两层循环遍历dp二维数组，即需要三重循环。

4.注意最优化问题中dp数组内元素的初始状态。因为这道题是求最小值，而且滚动数组优化后会从非数组首元素开始循环，所以我赋初值时给所有dp元素取了一个尽可能大的值：99999。另外，dp[0][0]要赋值为0，理由上面解释过了。

综上分析，最终我写出的代码为：

class Solution {
public:    
    int size;
    int minCost(int breadNum, int beverageNum, vector<vector<int> >& packageSum) {
        // write code here
        size = packageSum.size();   //行数（可选的捆绑产品数）
        int dp[breadNum+1][beverageNum+1];   //dp[i][j]:当需要i个面包和j个饮料时花费的最少钱
        for(int i=0;i<=breadNum;i++)
        {
            for(int j=0;j<=beverageNum;j++)
            {
                dp[i][j] = 99999;
            }
        }
        dp[0][0] = 0;
        for(int k=0;k<size;k++)    //第一层循环，遍历所有货品
        {
            for(int i=breadNum;i>=0;i--)    //第二层循环，枚举需要的面包数
            {     //倒序原因：滚动数组策略，省略了上一个货品时的空间，即当前dp[i][j]实际保存的是上一个货品dp的状态
                for(int j=beverageNum;j>=0;j--)     //二维背包问题，三维数组滚动优化为二维数组
                {
                    dp[i][j] = min(dp[i][j],
                       dp[max(i-packageSum[k][0],0)][max(j-packageSum[k][1],0)]
                                   +packageSum[k][2]);
                }
            }
        }
        return dp[breadNum][beverageNum];
    };

按照如上代码，终于得以通过。。。

总结：以后还是要多多练习动态规划，找准DP数组需要表达的含义，以及根据问题正确列出对应的状态转移方程，才是重中之重！！！

发表于 2020-07-22 00:15:34 回复(0)

lazywg

假设需要面包n个，饮料m个。每个包装内面包x个，饮料y个。面包最少需要n/x，饮料最少需要m/y，取最少需要里最大的计算另一个是否满足需要满足情况如下: 1:面包最少需要大，需要最少套装数 n/x 2:饮料最少需要大，需要最少套装数m/y 不满足情况如下: 1:面包最少需要大，需要最少套装数(m-(n/x)*y)/y + n/x 2:饮料最少需要大，需要最少套装数(n-(m/y)*x)/x+m/y

发表于 2020-08-30 11:01:42 回复(0)