LintCode 1915. 举重（01背包）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

奥利第一次来到健身房，她正在计算她能举起的最大重量。 杠铃所能承受的最大重量为maxCapacity，健身房里有 n 个杠铃片，第 i 个杠铃片的重量为 weights[i]。 奥利现在需要选一些杠铃片加到杠铃上，使得杠铃的重量最大，但是所选的杠铃片重量总和又不能超过 maxCapacity ，请计算杠铃的最大重量是多少。

比如，给定杠铃片的重量为 weights = [1, 3, 5]， 而杠铃的最大承重为 maxCapacity = 7，那么应该选择重量为 1 和 5 的杠铃片，(1 5 = 6)，所以最终的答案是 6。

https://www.lintcode.com/problem/lifting-weights/description

2. 解题

代码语言：javascript复制

class Solution {
public:
    /**
     * @param weights: An array of n integers, where the value of each element weights[i] is the weight of each plate i
     * @param maxCapacity: An integer, the capacity of the barbell
     * @return: an integer denoting the maximum capacity of items that she can lift.
     */
    int weightCapacity(vector<int> &weights, int maxCapacity) {
        // Write your code here
        int n = weights.size();
        vector<bool> dp(maxCapacity 1, false);
        dp[0] = true;
        int maxW = 0;
        for(int i = 0; i < n;   i)
        {
            for(int j = maxCapacity-weights[i]; j>=0; --j)
            {	//逆序遍历，新状态不会干扰前面待遍历的旧状态
                if(dp[j])// j 重量状态存在
                {
                    dp[j weights[i]] = true;
                    maxW = max(maxW, j weights[i]);
                }
            }
        }
        return maxW;
    }
};

1307 ms C

---

c++ max

0 人点赞