[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]
7
输出：
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