题解 | #购物单#

购物单

http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

题目主要信息

1、从m个物品中选出若干个,其总价低于N

2、物品分为主件与附件,如果要买为附件的物品,必须先买该附件所属的主件

3、使得每件物品的价格与重要度的乘积的总和最大

方法一:动态规划

具体方法

本题很明显是一道01背包问题,对于这种问题,我们一般采用动态规划的方法来进行解决。我们定义动规数组f[i][j]来表示前i件物品,容量为j时的最大价值,则

f[i][j]={max(f[i1][j],f[i1][jw[i]]+v[i])jw[i]f[i1][j]elsef[i][j]=\begin{cases}\max(f[i-1][j], f[i-1][j-w[i]]+v[i]) & j \geq w[i]\\f[i-1][j] & else\end{cases}

在本题中进行了一项变动,即物品分为主件和附件,考虑到一个主件最多可以购买两个附件,那我们可以细化分析,将是否购买该物品,细化为是否购买该物品,以及是否购买该物品的附件,即5种情况,不购买该物品,购买该物品,购买该物品及附件1,购买该物品及附件2,购买该物品及附件1及附件2,f[i][j]取这五种情况的最大值,这五种情况分别对应于

f[i1][j]f[i-1][j]

f[i1][jw[i]]+v[i]f[i-1][j-w[i]]+v[i]

f[i][j]=max(f[i1][j],f[i1][jw[i]w[a1]]+v[i]+v[a1])f[i][j]=max(f[i-1][j], f[i-1][j-w[i]-w[a_1]]+v[i]+v[a_1])

f[i][j]=max(f[i1][j],f[i1][jw[i]w[a2]]+v[i]+v[a2])f[i][j]=max(f[i-1][j], f[i-1][j-w[i]-w[a_2]]+v[i]+v[a_2])

f[i][j]=max(f[i1][j],f[i1][jw[i]w[a1]w[a2]]+v[i]+v[a1]+v[a2])f[i][j]=max(f[i-1][j], f[i-1][j-w[i]-w[a_1]-w[a_2]]+v[i]+v[a_1]+v[a_2])

其中a1a_1a2a_2是该物品的附件。

下面用一个示例来说明,各个颜色表示最优方案,其中白块表示初始化区域,绿块表示不取物品最大,红块表示只取物品主件,紫块表示取物品主件和附件1,黄块表示取物品主件和附件2,蓝块表示取物品主件和两个附件 alt

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int m = sc.nextInt();

        Goods[] goods = new Goods[m];
        for(int i = 0; i < m; i++){
            goods[i] = new Goods();
        }
        for(int i = 0; i < m; i++){
            int v = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            goods[i].v = v;
            goods[i].p = p * v;  // 直接用p*v,方便后面计算
            if(q==0){
                goods[i].main = true;
            }else if(goods[q-1].a1 == -1){
                goods[q-1].a1 = i;
            }else{
                goods[q-1].a2 = i;
            }
        }

        int[][] dp = new int[m+1][N+1];
        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= N; j++){
                dp[i][j] = dp[i-1][j];
                if(!goods[i-1].main){
                    continue;
                }
                if(j>=goods[i-1].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i-1].v] + goods[i-1].p);
                }
                if(goods[i-1].a1 != -1 && j >= goods[i-1].v + goods[goods[i-1].a1].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i-1].v - goods[goods[i-1].a1].v] + goods[i-1].p + goods[goods[i-1].a1].p);
                }
                if(goods[i-1].a2 != -1 && j >= goods[i-1].v + goods[goods[i-1].a2].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i-1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a2].p);
                }
                if(goods[i-1].a1 != -1 && goods[i-1].a2 != -1 &&  j >= goods[i-1].v + goods[goods[i-1].a1].v + goods[goods[i-1].a2].v){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i-1].v - goods[goods[i-1].a1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a1].p + goods[goods[i-1].a2].p);
                }
            }
        }
        System.out.println(dp[m][N]);
    }
}

class Goods {
    int v;
    int p;
    boolean main = false;

    int a1 = -1;  //定义附件1的编号
    int a2 = -1;  //定义附件2的编号
}

复杂度分析

  • 时间复杂度:O(mN)O(m*N),双层循环
  • 空间复杂度:O(mN)O(m*N),需要一个二维额外数组

方法二:动态规划(空间压缩)

具体方法

基本与思路一一样,但是在本题中,由于我们是否取第i个商品时的数组只与是否取第i-1个商品时的数组相关,所以可以进行空间压缩,将时间复杂度压缩到O(N)O(N),但需注意逆循环,防止前面修改被后面应用。

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int m = sc.nextInt();

        Goods[] goods = new Goods[m];
        for(int i = 0; i < m; i++){
            goods[i] = new Goods();
        }
        for(int i = 0; i < m; i++){
            int v = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            goods[i].v = v;
            goods[i].p = p * v;  // 直接用p*v,方便后面计算
            if(q==0){
                goods[i].main = true;
            }else if(goods[q-1].a1 == -1){
                goods[q-1].a1 = i;
            }else{
                goods[q-1].a2 = i;
            }
        }

        int[] dp = new int[N+1];
        for(int i = 1; i <= m; i++){
            for(int j = N; j >= 0; j--){
                if(!goods[i-1].main){
                    continue;
                }
                if(j>=goods[i-1].v){
                    dp[j] = Math.max(dp[j], dp[j-goods[i-1].v] + goods[i-1].p);
                }
                if(goods[i-1].a1 != -1 && j >= goods[i-1].v + goods[goods[i-1].a1].v){
                    dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a1].v] + goods[i-1].p + goods[goods[i-1].a1].p);
                }
                if(goods[i-1].a2 != -1 && j >= goods[i-1].v + goods[goods[i-1].a2].v){
                    dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a2].p);
                }
                if(goods[i-1].a1 != -1 && goods[i-1].a2 != -1 &&  j >= goods[i-1].v + goods[goods[i-1].a1].v + goods[goods[i-1].a2].v){
                    dp[j] = Math.max(dp[j], dp[j-goods[i-1].v - goods[goods[i-1].a1].v - goods[goods[i-1].a2].v] + goods[i-1].p + goods[goods[i-1].a1].p + goods[goods[i-1].a2].p);
                }
            }
        }
        System.out.println(dp[N]);
    }
}

class Goods {
    int v;
    int p;
    boolean main = false;

    int a1 = -1;  //定义附件1的编号
    int a2 = -1;  //定义附件2的编号
}

复杂度分析

  • 时间复杂度:O(mN)O(m*N),双层循环
  • 空间复杂度:O(N)O(N),只需要一维数组保存状态
华为机试 文章被收录于专栏

本专栏主要用于分享华为机试的题解,希望对大家有所帮助。

全部评论
为什么dp数组不用初始化?
2 回复 分享
发布于 2022-07-30 13:36
dp[i][j] = dp[i-1][j]; 那位大佬指点一下,这个i不是代表的第i个物品吗? 为什么要把i-1的物品j元钱时的最大价值给到 i物品j元时呢?
点赞 回复 分享
发布于 2022-09-01 21:10 北京
看明白了,写的很好! 与通常背包问题不同,这里做选择时,附件物品不单独考虑,而是在选取主键时就考虑是否购买附件。 关键差别在于:对于新加进来的一件物品, 1.通常0-1背包问题,选择只有【2种】:购买该物品,不购买该物品。 2.本题:如果是附件,直接跳过,附件不做选择(结果与上一个主件购买结果一样)。主件物品选择有【5种】,即为答主所列5种。
4 回复 分享
发布于 2022-06-05 17:54
方法二可以直接用goods[i],而且j的for循环可以直接每次j-=10,j--浪费了一大半时间
2 回复 分享
发布于 2023-02-18 05:33 以色列
附件1和2的颜色反了?
1 回复 分享
发布于 2022-07-13 22:09
有没有大神帮忙解答下,方法二的第二层for循环内,判断不是附件的三个if语句中,求dp[j]时都有 +dp[j-主件价格-附件价格],这段代码是什么意思。
点赞 回复 分享
发布于 04-08 11:59 北京
没注释的代码真要命
点赞 回复 分享
发布于 2024-12-13 11:48 陕西
终于整明白了,困惑了两天
点赞 回复 分享
发布于 2024-05-28 11:17 北京
看懂了 大神牛逼
点赞 回复 分享
发布于 2024-04-13 23:38 湖北
我的错误,要注意if(条件1 && 条件2)的顺序,条件1判断附件=-1必须写在前面,不然会出现gs[-1]数组越界的错误
点赞 回复 分享
发布于 2023-10-25 19:45 浙江
为什么二维数组要多出来一行一列呢?i=0意思是不选择该物品?j=0呢?int[][] dp = new int[i+1][j+1];
点赞 回复 分享
发布于 2023-10-25 17:30 浙江
代码很清晰,比前面那个写python的老哥好多了
点赞 回复 分享
发布于 2023-05-13 11:04 浙江
感觉不是很对啊,如果最后一行物品是组件呢?能直接认为最后一行组件不用买吗?
点赞 回复 分享
发布于 2023-03-21 19:10 上海
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-goods[i-1].v] + goods[i-1].p)这里没理解。求大神解答。不应该是dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-goods[i-1].v] + goods[i-1].p)吗?
点赞 回复 分享
发布于 2022-12-24 11:11 广东
大佬们能否指点一下,我也是在dp[i][j] = dp[i-1][j]这个地方想了一小时了没想通,为什么要把i-1的物品j元钱时的最大价值给到 i物品j元时呢?大佬们可否指定迷津
点赞 回复 分享
发布于 2022-11-11 18:14 广东
自测的预计输出是怎么回事??
点赞 回复 分享
发布于 2022-08-22 06:53 广西
现在过不了,测试用例了
点赞 回复 分享
发布于 2022-08-09 15:37
5400的颜色标注是不是错误了
点赞 回复 分享
发布于 2022-07-15 16:48
原来是运行了上一次的
点赞 回复 分享
发布于 2022-07-14 18:17
真奇怪,IDEA上不是 短路与 也行;改过来就好了
点赞 回复 分享
发布于 2022-07-14 18:14

相关推荐

评论
131
40
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务