[leetcode/lintcode 题解] 阿里算法面试真题详解：举重

描述
奥利第一次来到健身房，她正在计算她能举起的最大重量。杠铃所能承受的最大重量为maxCapacity，健身房里有n个杠铃片，第 i 个杠铃片的重量为 weights[i]。奥利现在需要选一些杠铃片加到杠铃上，使得杠铃的重量最大，但是所选的杠铃片重量总和又不能超过 maxCapacity ，请计算杠铃的最大重量是多少。
比如，给定杠铃片的重量为 weights = [1, 3, 5]， 而杠铃的最大承重为 maxCapacity = 7，那么应该选择重量为 1 和 5 的杠铃片，(1 + 5 = 6)，所以最终的答案是 6。
1≤n≤42
1≤maxCapacity≤106
1≤weights[i]≤106

在线评测地址：领扣题库官网

样例1
[1,3,5]
6

解题思路
经典的背包问题。
状态：dp[j] 表示是否存在一种杠铃片的选择方案使杠铃的重量达到 j 初始化：dp[0] = true 如果一个杠铃片都不选，杠铃的重量就是 0 转移：dp[j] = dp[j] || dp[j - weight[i]] 如果已经存在一种方案可以是杠铃的重量达到 j 或 j - weight[i] 答案：dp[maxCapacity]

复杂度分析
时间复杂度：O(n * maxCapacity)
枚举每个杠铃片 O(n)，枚举每个重量 O(maxCapacity)。两者是嵌套关系，所以是O(n * maxCapacity)
空间复杂度：O(maxCapacity)
dp数组的空间耗费

源代码

public class Solution {
 * @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.
 public int weightCapacity(int[] weights, int maxCapacity) {
 boolean[] dp = new boolean[maxCapacity + 1];
 dp[0] = true;
 int answer = 0;
 for (int i = 0; i weights.length; i++) {
 int weight = weights[i];
 for (int j = maxCapacity; j = weight; j--) {
 if (dp[j - weight]) {
 dp[j] = true;
 answer = Math.max(answer, j);
 return answer;
}

更多题解参考：九章官网solution

本文转自网络，原文链接：https://developer.aliyun.com/article/784243
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！