牛客 牛牛选物（01背包）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

链接：https://ac.nowcoder.com/acm/contest/9887/A 来源：牛客网

牛牛有现在有n个物品，每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品，想使这若干个物品的总重量最大，他想知道最大总重量为多少。（如果不存在合法方案，返回-1）

2. 解题

• 数据范围 V 很大，开DP数组要超时，采用哈希表

代码语言：javascript复制

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
     * @param v int整型vector 
     * @param g int整型vector 
     * @param V int整型 
     * @return int整型
     */
    int Maximumweight(vector<int>& v, vector<int>& g, int V) {
        // write code here
        int n = v.size();
        unordered_map<int, int> dp;// V G
        dp[0] = 0;
        dp[v[0]] = g[0];
        for(int i = 1; i < n; i  ) 
        {
            unordered_map<int, 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(vi v[i]) == temp.end())
                        temp[vi v[i]] = gi   g[i];
                    else
                        temp[vi v[i]] = max(temp[vi v[i]], gi   g[i]);
                }
            }
            dp.swap(temp);
        }
        if(dp.find(V) == dp.end()) return -1;
        return dp[V];
    }
};

585ms C

---

c++ dp 数组

0 人点赞