安徽建站,wordpress logo 编辑器,wordpress初始登录,北京短视频拍摄公司文章目录1. 题目2. 解题1. 题目
奥利第一次来到健身房#xff0c;她正在计算她能举起的最大重量。 杠铃所能承受的最大重量为maxCapacity#xff0c;健身房里有 n 个杠铃片#xff0c;第 i 个杠铃片的重量为 weights[i]。 奥利现在需要选一些杠铃片加到杠铃上#xff0c;使…
文章目录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. 解题
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(vectorint weights, int maxCapacity) {// Write your code hereint n weights.size();vectorbool dp(maxCapacity1, false);dp[0] true;int maxW 0;for(int i 0; i n; i){for(int j maxCapacity-weights[i]; j0; --j){ //逆序遍历新状态不会干扰前面待遍历的旧状态if(dp[j])// j 重量状态存在{dp[jweights[i]] true;maxW max(maxW, jweights[i]);}}}return maxW;}
};1307 ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
