蚂蚁春招-2023.3.16-组装电脑-中等-Toy模板网

这篇具有很好参考价值的文章主要介绍了蚂蚁春招-2023.3.16-组装电脑-中等。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

组装电脑

Problem Description

小红准备买一些零件来组装电脑。已知电脑一共有n个零件，每个零件有若干个型号。小红现在知道了每个型号的对应价格 $a_{i}$ ,以及性能 $v_{i}$ 。小红需要每个零件选择一个型号，在总价格不超过x元的前提下，最终的总性能尽可能大。你能帮帮她吗?

input

第一行输入两个正整数n和x，代表电脑的零件数量以及小红最大的预算。接下来的3∗n行，每三行用来描述一个零件的不同型号的价格和性能。
对于每个零件，第一行输入一个正数m，代表该零件有多少种型号。 $1≤n,m≤40,1≤a_i ,v_i ,x≤10^9$
保证所有m之和不超过40，即所有零件的型号数保证所有m之和不超过40，即所有零件的型号数量之和不超过40种。

ouput

如果无法完成组装，则直接输出-1。否则输出一个正整数，代表最终最大的性能。

Sample Input

2 4
2
1 2
3 5
3
3 2 3
5 6 7

Sample Output

11文章来源地址https://www.toymoban.com/news/detail-493921.html

题目类型、难度、来源

类型：动态规划
难度：中等
来源：蚂蚁春招-2023.3.16-组装电脑

总体思路：

使用动态规划。 $d p [i] [j]$ 表示买前i个零件，共花了j元（i从1算起，i=0表示没有零件）获得的最大性能。 $cos t [i], p er f [i]$ 分别表示第i个零件的价格和性能。
边界条件： $d p [0] [0] = 0$ ，表示买前０个零件，共花了０元，性能是０。
状态转移方程： $dp[i][j]=max{\{dp[i-1][j-cost[0]]+perf[0], dp[i-1][j-cost[1]]+perf[1], ...\}}$
这个方程比较难计算，我们可以反过来思考。
- 可以使用 $d p [i] [j]$ 去更新 $d p [i + 1] [j + cos t [0]]$ 、 $d p [i + 1] [j + cos t [1]]$ 等等。
- 具体的： $d p [i + 1] [j + cos t [0]] = ma x (d p [i + 1] [j + cos t [0]], d p [i] [j] + p er f [0])$
  - 这个公式需要不断被刷新，因为 $d p [i + 1] [j + cos t [0]]$ 的值和多个dp数组值有关。
完成上述推理后，我们开始写代码，却发现x的只最大可以达到 $10^9$ ，如果使用传统方法做动态规划，这肯定就不行了，因为开不了那么大的数组。为了解决这个问题，我们可以使用map充当数组。

AC代码

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main(){
    int n, x;
    cin >> n >> x;
    int **cost = new int*[n];
    int **perf = new int*[n];
    int *comp_nums = new int[n];
    for (int t = 0; t < n; t++){
        cin >> comp_nums[t];
        cost[t] = new int[comp_nums[t]];
        perf[t] = new int[comp_nums[t]];
        for (int i = 0; i < comp_nums[t]; i++){
            cin >> cost[t][i];
        }
        for (int i = 0; i < comp_nums[t]; i++){
            cin >> perf[t][i];
        }
    }
    map<long long, long long> dp[45];
    dp[0][0] = 0;
    long long max_perf = -1;
    for (long long t = 0; t < n; t++){
        for (auto iter = dp[t].begin(); iter != dp[t].end(); iter++){
            long long dp_cost = iter->first;
            long long dp_perf = iter->second;
            for (long long i = 0; i < comp_nums[t]; i++){
                if (dp_cost+cost[t][i] <= x){
                    dp[t+1][dp_cost+cost[t][i]] = max(dp[t+1][dp_cost+cost[t][i]], dp_perf+perf[t][i]);
                    if ((t+1 == n) && (dp[t+1][dp_cost+cost[t][i]] > max_perf)){
                        max_perf = dp[t+1][dp_cost+cost[t][i]];
                    }
                }
            }
        }
    }
    cout << max_perf;
    return 0;
}