52. 携带研究材料(第七期模拟笔试)

52. 携带研究材料(第七期模拟笔试)

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

题目描述

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

小明的行李箱所能承担的总重量为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料可以选择无数次,并且可以重复选择。

输入描述

第一行包含两个整数,N,V,分别表示研究材料的种类和行李空间
接下来包含 N 行,每行两个整数 wi 和 vi,代表第 i 种研究材料的重量和价值

输出描述

输出一个整数,表示最大价值。

输入示例

4 5
1 2
2 4
3 4
4 5

输出示例

10

提示信息

第一种材料选择五次,可以达到最大值。

数据范围:

1 <= N <= 10000;
1 <= V <= 10000;
1 <= wi, vi <= 10^9.

代码如下:

#include <bits/stdc++.h>
using namespace std;

//完全背包,,完全背包的物品是可以添加多次的
void test_CompletePack(const vector<int>& weight,const vector<int>& value,int bagWeight)
{
    vector<int> dp(bagWeight+1,0);
    //在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的!
    for(int j=0;j<=bagWeight;j++)// 遍历背包容量
    {
        for(int i=0;i<weight.size();i++)// 遍历物品
        {
            if(j-weight[i]>=0)
                dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[bagWeight]<<endl;
}

int main()
{
    int N,V;
    cin>>N>>V;
    vector<int> weight;
    vector<int> value;
    for(int i=0;i<N;i++)
    {
        int w,v;
        cin>>w>>v;
        weight.emplace_back(w);
        value.emplace_back(v);
    }
    test_CompletePack(weight,value,V);
    return 0;
}

最近更新

  1. TCP协议是安全的吗?

    2024-03-17 10:16:02       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-03-17 10:16:02       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-03-17 10:16:02       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-03-17 10:16:02       18 阅读

热门阅读

  1. kotlin flow sample的用法

    2024-03-17 10:16:02       16 阅读
  2. ChatGPT:突破写作限制,开启论文写作新境界

    2024-03-17 10:16:02       18 阅读
  3. axios入门

    2024-03-17 10:16:02       17 阅读
  4. LeetCode题练习与总结:解数独

    2024-03-17 10:16:02       19 阅读
  5. Axios 中的文件上传(Upload File)方法

    2024-03-17 10:16:02       18 阅读
  6. linux系统kubernetes的yaml文件

    2024-03-17 10:16:02       21 阅读
  7. CMake官方教程9--打包文件

    2024-03-17 10:16:02       19 阅读