成都做网站优化价格,做网站用那种数据库,如何用python做一个网站,什么网站教做医学实验报告文章目录1. 题目2. 解题1. 题目
链接#xff1a;https://ac.nowcoder.com/acm/contest/9887/A 来源#xff1a;牛客网
牛牛有现在有n个物品#xff0c;每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品#xff0c;想使这若干个物品的总重量最大https://ac.nowcoder.com/acm/contest/9887/A 来源牛客网
牛牛有现在有n个物品每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品想使这若干个物品的总重量最大他想知道最大总重量为多少。如果不存在合法方案返回-1 2. 解题
数据范围 V 很大开DP数组要超时采用哈希表
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 返回总体积为V若干物品的最大总重量如果g存在选择若干物品总体积为V的情况返回-1* param v int整型vector * param g int整型vector * param V int整型 * return int整型*/int Maximumweight(vectorint v, vectorint g, int V) {// write code hereint n v.size();unordered_mapint, int dp;// V Gdp[0] 0;dp[v[0]] g[0];for(int i 1; i n; i) {unordered_mapint, int temp(dp.begin(), dp.end());for(auto it dp.begin(); it ! dp.end(); it){int vi it-first;int gi it-second;if(vi v[i] V){if(temp.find(viv[i]) temp.end())temp[viv[i]] gi g[i];elsetemp[viv[i]] max(temp[viv[i]], gi g[i]);}}dp.swap(temp);}if(dp.find(V) dp.end()) return -1;return dp[V];}
};585ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
