题解 | #牛妹的春游#

题意整理

• 给定x，y，以及若干数对[ai,bi,ci]。
• 从中选出部分数对，使得ai数对的和不小于x，bi数对的和不小于y，求最小的ci数对的和。

方法一（动态规划）

1.解题思路

• 状态定义：dp[i][j][k]表示选择包装数为i，面包数为j，饮料数为k的情况下，最小的花费。
• 状态初始化：不选择任何包装时，花费为0。
• 状态转移：如果j大于等于breadNum是正常的01背包问题，直接从背包取，如果j小于breadNum，仍然从背包取，只是应该从状态为0的位置转移，对于k的分析也是类似。即 。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param breadNum int整型 
     * @param beverageNum int整型 
     * @param packageSum int整型二维数组 每个一维数组中有三个数，依次表示这个包装里面的面包数量、饮料数量、花费
     * @return int整型
     */
    public int minCost (int breadNum, int beverageNum, int[][] packageSum) {
        int n=packageSum.length;
        /*初始化dp数组，第一维表示当前包装数量，第二维表示面包数，
        第三维表示饮料数，整体表示当前最小的花费*/
        int[][][] dp=new int[n+1][breadNum+1][beverageNum+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=breadNum;j++){
                Arrays.fill(dp[i][j],Integer.MAX_VALUE/2);
            }
        }
        //不选择任何包装时，花费为0
        dp[0][0][0]=0;

        for(int i=1;i<=n;i++){
            for(int j=0;j<=breadNum;j++){
                for(int k=0;k<=beverageNum;k++){
                    //当前费用至少需要前一次费用的数值
                    dp[i][j][k]=dp[i-1][j][k];
                    /*如果j大于等于breadNum是正常的01背包问题，直接从背包取
                      如果j小于breadNum，仍然从背包取，只是应该从状态为0的位置转移
                      对k这一层的维度也是类似的分析过程*/
                    dp[i][j][k]=Math.min(dp[i][j][k]
                                      ,dp[i-1][Math.max(j-packageSum[i-1][0],0)][Math.max(k-packageSum[i-1][1],0)]
                                      +packageSum[i-1][2]);
                }
            }
        }

        return dp[n][breadNum][beverageNum];
    }
}

3.复杂度分析

• 时间复杂度：假设输入面包的数目为breadNum，饮料的数目为beverageNum，包装的数量为n，则时间复杂度为。
• 空间复杂度：需要额外大小为的dp数组，所以空间复杂度为。

方法二（空间压缩）

1.解题思路

基本思路和方法一相同，另外可以通过滚动数组的方式降低一维空间的开销，同时为了避免重复计算，需要逆序遍历。

动图展示（测试的输入数据为：2,2,[[1,3,12],[1,2,15],[2,1,20]]）：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param breadNum int整型 
     * @param beverageNum int整型 
     * @param packageSum int整型二维数组 每个一维数组中有三个数，依次表示这个包装里面的面包数量、饮料数量、花费
     * @return int整型
     */
    static final int INF=Integer.MAX_VALUE/2;

    public int minCost (int breadNum, int beverageNum, int[][] packageSum) {
        /*初始化dp数组，第一维表示面包数，
        第二维表示饮料数，整体表示当前最小的花费*/
        int[][] dp=new int[breadNum+1][beverageNum+1];
        for(int i=0;i<=breadNum;i++){
            Arrays.fill(dp[i],INF);
        }
        //不选择任何包装时，花费为0
        dp[0][0]=0;
        int n=packageSum.length;
        for(int i=0;i<n;i++){
            for(int j=breadNum;j>=0;j--){
                for(int k=beverageNum;k>=0;k--){
                    //通过逆序的方式跟新状态，防止重复计算，同时节省了一维空间
                    dp[j][k]=Math.min(dp[j][k]
                                      ,dp[Math.max(j-packageSum[i][0],0)][Math.max(k-packageSum[i][1],0)]
                                      +packageSum[i][2]);
                }
            }
        }

        return dp[breadNum][beverageNum];
    }
}

3.复杂度分析

• 时间复杂度：假设输入面包的数目为breadNum，饮料的数目为beverageNum，包装的数量为n，则时间复杂度为。
• 空间复杂度：需要额外大小为的dp数组，所以空间复杂度为。