leetcode416. Partition Equal Subset Sum

Caicloud 發布于2019-08-16 15:10 / 1818人閱讀

摘要：題目要求假設有一個全為正整數的非空數組，將其中的數字分為兩部分，確保兩部分數字的和相等。而這里的問題等價于，有個物品，每個物品承重為，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。

題目要求

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
1.Each of the array element will not exceed 100.
2.The array size will not exceed 200.
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

假設有一個全為正整數的非空數組，將其中的數字分為兩部分，確保兩部分數字的和相等。

思路和代碼

這和0-1背包問題是完全一樣的，01背包問題是指假設有n個物品，每個物品中為weight[i]，假設背包的承重為k，問如何選擇物品使得背包中的承重最大。而這里的問題等價于，有n個物品，每個物品承重為input[i]，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。

假設我們已經知道前i個物品是否能夠構成重量k，我們令該值為dpi，那么第i+1個物品是否能夠構成重量取決于dpi和dpi], 即i+1個物品能夠構成重量k有兩種情況，第一種選擇了i+1個物品，則要尋找前i個物品是否構成k-input[i+1]的重量，第二種就是沒有選擇第i+1個物品，則直接判斷前i個物品是否已經構成了k的重量。

代碼如下：

    public boolean canParition(int[] nums) {
        int sum = 0;
        for(int n : nums) {
            sum += n;
        }
        if(sum % 2 != 0) return false;
        int half = sum / 2;
        boolean[][] sums = new boolean[nums.length+1][half+1];
        for(int i = 0 ; i<=nums.length ; i++) {
            for(int j = 0 ; j<=half ; j++) {
                if(i==0 && j==0){
                    sums[i][j] = true;
                }else if(i==0) {
                    sums[i][j] = false;
                }else if(j==0){
                    sums[i][j] = true;
                }else {
                    sums[i][j] = sums[i-1][j] || (nums[i-1] <= j ? sums[i-1][j-nums[i-1]] : false);
                }
            }
        }
        return sums[nums.length][half];
    }

GPU云服務器云服務器 Subset equal mvc416 Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/73313.html

leetcode 416 Partition Equal Subset Sum

摘要：如果是奇數的話，那一定是不滿足條件的，可以直接返回。如果是偶數，將除獲得我們要求的一個子數組元素的和。如何暫存我們計算的中間結果呢聲明一個長度為的布爾值數組。每個元素的布爾值代表著，數組中是否存在滿足加和為的元素序列。題目詳情 Given a non-empty array containing only positive integers, find if the array ca...

jsummer 2019-08-16 11:07 評論0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 評論0 收藏0
[Leetcode - Dynamic Programming] Partition Equal S

摘要：背包問題假設有個寶石，只有一個容量為的背包，且第個寶石所對應的重量和價值為和求裝哪些寶石可以獲得最大的價值收益思路我們將個寶石進行編號，尋找的狀態和狀態轉移方程。我們用表示將前個寶石裝到剩余容量為的背包中，那么久很容易得到狀態轉移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

qpal 2019-08-14 16:41 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LeetCode] 698. Partition to K Equal Sum Subsets

Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...

kuangcaibao 2019-08-16 13:41 評論0 收藏0