携带研究材料(第六期模拟笔试)

发布时间:2024年01月17日

时间限制:5.000S 空间限制:128MB

题目描述

小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。

小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。

输入描述

第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。

第二行包含 M 个正整数,代表每种研究材料的所占空间。

第三行包含 M 个正整数,代表每种研究材料的价值。

输出描述

输出一个整数,代表小明能够携带的研究材料的最大价值。

输入示例

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

输出示例

5

提示信息

小明能够携带 6 种研究材料,但是行李空间只有 1,而占用空间为 1 的研究材料价值为 5,所以最终答案输出 5。

数据范围:

1 <= N <= 1000
1 <= M <= 1000
研究材料占用空间和价值都小于等于 1000

题解

这个题是经典的01背包问题。对于第i种材料,如果当前背包容量可以装下,那我们就考虑拿还是不拿,如果拿了价值更大,那就拿,不然就不拿,可以得到状态转移方程为:

 			if(j < w[i]) {
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }

唯一要注意的就是这个题题目测试用例最大为5000,并不是题目所说的1000.

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int dp[N][N] = {0},w[N] = {0},v[N] = {0};

int main(){
    int m,n;
    cin >> m >> n;
    for(int i = 1;i <= m; i++){
        cin >> w[i];
    }
    for(int i = 1;i <= m; i++){
        cin >> v[i];
    }
    for(int i = 1;i <= m; i++){
        for(int j = 0;j <= n; j++){
            if(j < w[i]) {
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[m][n];
    return 0;
}
文章来源:https://blog.csdn.net/L6666688888/article/details/135647613
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。