题解 | #购物单#

购物单

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

#include <iostream>
using namespace std;
#include <vector>
int main() {
    int N, m; // N为总钱数,m为总物品数
    cin >> N >> m;
    int v[m];    // 记录物品价格
    int w[m];    // 记录物品重要度
    int type[m]; // 记录物品主附属性
    int t;
    // 读取物品信息,i+1为该物品的编号
    for (int i = 0; i < m; i++) {
        cin >> v[i] >> w[i] >> t;
        type[i] = t - 1; // 将编号转化为数组下标
    }

    vector<vector<int>> vmap(61, vector<int>(4,
                             0)); // 记录主键4种情况所需的价格
    vector<vector<int>> wmap(61, vector<int>(4,
                             0)); // 记录主键4种情况所给予的重要度


    for (int i = 0; i < m; i++) {
        // 若为主键
        if (type[i] == -1) {
            // 初始化第一种情况——只有主键
            vmap[i][0] = v[i];
            wmap[i][0] = v[i] * w[i];
            for (int j = 0; j < m; j++) {
                // 检索到附件
                if (type[j] == i) {
                    // 第一次检索到附件
                    if (vmap[i][1] == 0) {
                        vmap[i][1] = vmap[i][0] + v[j];
                        wmap[i][1] = wmap[i][0] + v[j] * w[j];
                    }
                    // 第二次检索到附件
                    else {
                        vmap[i][2] = vmap[i][0] + v[j];
                        wmap[i][2] = wmap[i][0] + v[j] * w[j];

                        vmap[i][3] = vmap[i][1] + v[j];
                        wmap[i][3] = wmap[i][1] + v[j] * w[j];
                    }
                }
            }
        }
    }

    // 创建动态规划数组
    vector<vector<int>> dp(m + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < N + 1; j++) {

            //初始化第一行
            if (i == 0 ) {
                dp[i][j] = j >= vmap[i][0] ? wmap[i][0] : 0;
                dp[i][j] = j >= vmap[i][1] ? max(wmap[i][1], dp[i][j]) : dp[i][j];
                dp[i][j] = j >= vmap[i][2] ? max(wmap[i][2], dp[i][j]) : dp[i][j];
                dp[i][j] = j >= vmap[i][3] ? max(wmap[i][3], dp[i][j]) : dp[i][j];
            }

            if (i != 0 ) {
                dp[i][j] = j >= vmap[i][0] ? max(dp[i - 1][j],
                                                 dp[i - 1][j - vmap[i][0]] + wmap[i][0]) : dp[i - 1][j];
                dp[i][j] = j >= vmap[i][1] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][1]] + wmap[i][1]) : dp[i][j];
                dp[i][j] = j >= vmap[i][2] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][2]] + wmap[i][2]) : dp[i][j];
                dp[i][j] = j >= vmap[i][3] ? max(dp[i][j],
                                                 dp[i - 1][j - vmap[i][3]] + wmap[i][3]) : dp[i][j];

            }
        }
    }
    cout << dp[m - 1][N] << endl;
}

01背包问题的变种。

贴上01背包问题的笔记:

1 背包算法

概述

1.1 01背包算法

1.1.1 概述:
  • n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i],得到的价值是value[i]每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
  • 若使用暴力解法回溯,对于每种物品有放与不放2种状态,n个物品时间复杂度为2^n
1.1.2 dp数组的含义:
  • dp[i][j] 下标为[0,i]的物品任取,放进容量为j的背包里,所能达到的最大价值
  • 不放物品i, 背包容量为j,它所能装下物品的最大价值为dp[i-1][j]
  • 放一个物品i后,背包价值计算为dp[i-1][j-weight[i]] + value[i]
  • dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])从放物品i与不放物品i中选择最大的那个,作为dp[i][j]的值
1.1.3 dp数组表格如何初始化:
  • 一个元素,依赖于其正上方左上方的元素,先初始化第一行与第一列
  • 非零下标任意初始化,不影响

i 物品0

0

计算,最多为value[0]

计算,最多为value[0]

计算,最多为value[0]

物品1

0

物品2

0

物品3

0

1.1.4 遍历顺序:
  • 一般情况,两层for,外层遍历物品,第二层遍历背包容量,内部写dp公式 但是对于2维dp的两层for循环其实是可以颠倒的(满足上方和左上方有数据)

对于本问题,主要是分清楚每次放什么,对于附件不考虑单独情况,只考虑主件,对于每个主件最多有2个附件,一共4种情况:不带附件、带附件1、带附件2、带全部附件;对于每种情况选择最佳并且符合钱包的答案即可。提前计算一些数据,比如价格和价值存入数组中,方便dp时使用。

题目看了好久才看懂)

华为机试刷题记录 文章被收录于专栏

记录一下手打代码的解题思路方便复习

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-21 22:29
点赞 评论 收藏
分享
双非坐过牢:非佬,可以啊10.28笔试,11.06评估11.11,11.12两面,11.19oc➕offer
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务