[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