46. 携带研究材料（第六期模拟笔试）

本文主要是介绍46. 携带研究材料（第六期模拟笔试），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

46. 携带研究材料（第六期模拟笔试）

时间限制：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 <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

代码如下：

//参考：https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#%E6%80%9D%E8%B7%AF
#include <bits/stdc++.h>
using namespace std;//二维dp版
void solve1(int n,int bagweight)
{vector<int> weight(n,0);//存储物品的重量vector<int> value(n,0);//存储物品的价值for(int i=0;i<n;i++)cin>>weight[i];for(int i=0;i<n;i++)cin>>value[i];// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));// 初始化, 因为需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化为0// j >= weight[0]的值就初始化为value[0]for(int j=weight[0];j<=bagweight;j++)dp[0][j]=value[0];for(int i=1;i<weight.size();i++)//遍历物品{for(int j=0;j<=bagweight;j++)//遍历行李箱容量{if(j<weight[i]) dp[i][j]=dp[i-1][j];//放不下else//放得下dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}cout<<dp[weight.size()-1][bagweight]<<endl;
}//一维dp版
void solve2(int n,int bagweight)
{vector<int> weight(n,0);//存储物品的重量vector<int> value(n,0);//存储物品的价值for(int i=0;i<n;i++)cin>>weight[i];for(int i=0;i<n;i++)cin>>value[i];vector<int> dp(bagweight+1,0);// 外层循环遍历每个类型的研究材料for(int i=0;i<weight.size();i++){// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for(int j=bagweight;j>=weight[i];j--)//虑当前研究材料选择和不选择的情况，选择最大值dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}cout<<dp[bagweight]<<endl;
}int main()
{int n,bagweight;while(cin>>n>>bagweight){// solve1(n,bagweight);solve2(n,bagweight);}return 0;
}