0/1 knapsack detailed explanation


  • 98
    Z

    This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).

    Actually, this is a 0/1 knapsack problem, for each number, we can pick it or not. Let us assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.

    Base case: dp[0][0] is true; (zero number consists of sum 0 is true)

    Transition function: For each number, if we don't pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i]). If we pick nums[i]. dp[i][j] = dp[i-1][j-nums[i]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

    talking is cheap:

    public boolean canPartition(int[] nums) {
        int sum = 0;
        
        for (int num : nums) {
            sum += num;
        }
        
        if ((sum & 1) == 1) {
            return false;
        }
        sum /= 2;
    
        int n = nums.length;
        boolean[][] dp = new boolean[n+1][sum+1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], false);
        }
        
        dp[0][0] = true;
        
        for (int i = 1; i < n+1; i++) {
            dp[i][0] = true;
        }
        for (int j = 1; j < sum+1; j++) {
            dp[0][j] = false;
        }
        
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < sum+1; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
                }
            }
        }
       
        return dp[n][sum];
    }
    

    But can we optimize it? It seems that we cannot optimize it in time. But we can optimize in space. We currently use two dimensional array to solve it, but we can only use one dimensional array.

    So the code becomes:

    public boolean canPartition(int[] nums) {
        int sum = 0;
        
        for (int num : nums) {
            sum += num;
        }
        
        if ((sum & 1) == 1) {
            return false;
        }
        sum /= 2;
        
        int n = nums.length;
        boolean[] dp = new boolean[sum+1];
        Arrays.fill(dp, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int i = sum; i > 0; i--) {
                if (i >= num) {
                    dp[i] = dp[i] || dp[i-num];
                }
            }
        }
        
        return dp[sum];
    }
    

    For Chinese user: http://love-oriented.com/pack/P01.html is good explanation.


  • 0

    @ZhuEason thanks for the great solution and explanation.


  • 0
    T

    dp[i][0] why not False?
    because the specific sum 0 can't be gotten from the first i numbers,where i>0
    that is :
    for (int i = 1; i < n+1; i++) {
    dp[i][0] = true;
    }


  • 1
    Z

    @tongzhenguo Picking nothing means 0. Thus dp[i][0] = true


  • 0
    M

    Hi, thanks for your solution. But I think it's subset sum problem not knapsack


  • 5
    // here the concise version inspired by you
    
     public boolean canPartition(int[] nums) {
            int sum=0;
            for(int n:nums) sum+=n;
            if((sum&1)==1) return false;
            sum>>>=1;
            boolean[] dp=new boolean [sum+1];
            dp[0]=true;
            for(int k:nums){
                for(int j=sum;j>=k;j--)
                    dp[j]=dp[j]||dp[j-k];
            }
            return dp[sum];
        }
    

  • 1
    S

    How can you guys find that it is a dp problem because from my tuition it is a finding a subset problem?


  • 0
    D

    @ZhuEason Hello, ZhuEason, I learned a lot from your solution. And I have implemented one solution by using map<int, map> and memoized recursive function. However, it causes TLE which is opposite from my expectation (because I thought my method would be faster than calculating every element in 2D array). Could you help me with this please? My solution is at: https://discuss.leetcode.com/topic/81056/why-is-my-java-solution-tle


  • 0
    X

    @miracle2138 said in 0/1 knapsack detailed explanation:

    sum problem not knap

    Yes, I also think it's a subset problem. We need to ensure that there is only two subsets separated. If it's a dp problem, then as long as there are some numbers that can be added to the sum, it is true. It's quite confusing.


  • 0
    T

    In your optimized solution, you are declaring int n but never using it.


  • 4
    T

    Also, a boolean array is initialized with false values. So, your Array.fill step is not necessary.

    Additionally, why does your if condition test for > 0, if you are not even doing anything within it.

    Just replace it with

    for(int i = sum; i >= num; i--) {     
           dp[i] = dp[i] || dp[i - num] 
    }
    

  • 4
    T

    In your 1d DP array solution, why did you let i go from the right instead of left?


  • 0
    L

    @thepha3drus I understand the first solution but for the second one (with one dimensional bool array) I see we are looping from 'i=sum' to num (i.e higher to lower) but in the first solution we are looping from num to sum (lower to higher). I don't understand this part.. in both the dp equation we are referring to dp[CurrentSum - CurrentNum] so shouldn't we always loop from lowerSum to HigherSum? ..


  • 0
    X

    @dachuan.huang try this:

    public boolean canPartition(int[] nums) {
        int sum = IntStream.of(nums).sum();
        if (sum % 2 == 1) {
            return false;
        }
        
        sum /= 2;
        
        final Set<Integer> c = new HashSet<>();
        
        for (int num : nums) {
            for (int m : new ArrayList<>(c)) {
                if(m + num == sum) {
                    return true;
                } else if (m + num < sum) {
                    c.add(m + num);
                }
            }
            
            if (num == sum) {
                return true;
            } else {
                c.add(num);
            }
        }
        
        return false;
    }
    

  • 1
    N

    @lugok
    Transition function for 1d solution
    dp[i] = dp[i] || dp[i - nums[i]];
    dp[i] will depend on dp[i - nums[i]];
    "i" always large than "i - nums[i]" , we can't have dp[i-nums] be calculated and overwrite before we do it for dp[i]
    that's why the loop go from high to low.

    in 2d solution, we don't need to worry about intermediate result been overrite


  • 0

    I find it is not necessary to use Arrays.fill to set the dp matrix to false.
    The second loop of DP transaction can be written as following to avoid a statement

    for (int j = sum / 2; j >= nums[i - 1]; j--)
    The transaction in my program is dp[i - 1][j] other than dp[i][j].

    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];

    public class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int n: nums) {
                sum += n;
            }
            if (sum % 2 != 0) {
                return false;
            }
            // 2D DP initialization 
            boolean[][] dp = new boolean[nums.length + 1][sum / 2 + 1];
            dp[0][0] = true;
            for (int i = 1; i < nums.length + 1; i++) {
                dp[i][0] = true;
            }
            for (int j = 1; j < sum / 2 + 1; j++) {
                dp[0][j] = false;
            }
    
            // dp function
            for (int i = 1; i < nums.length + 1; i++) {
                for (int j = sum / 2; j >= nums[i - 1]; j--) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
    
            return dp[nums.length][sum / 2];
        }
    }
    

  • 0
    M

    @ZhuEason said in 0/1 knapsack detailed explanation:

    This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).

    How did you arrive at the conclusion that the sum of the set of number to be sum/2 ?


  • 0
    C

    @midhun7416 In order to get 2 subset with equal sum, the sum of subset A must be equal to sum of subset B.
    Since subset A and subset B come from nums array, we can conclude that

    sum(A) + sum(B) = sum(nums)

    And since sum(A) equal to sum(B), we get

    2 * sum(A) = sum(nums)
    or
    2 * sum(B) = sum(nums)

    Base on these 2 equation, we get sum of subset of A or B must be equal to sum(nums)/2

    sum(A) = sum(nums)/2


  • 0
    S

    @tongzhenguo Would you please explain why we should initialize dp[i][0] as true?
    How could we get sum 0 from first i - 1 element or i elements?


  • 0

    @sherry975 @ZhuEason Same confusion here.
    I can understand dp[0][0] = true; as if picking nothing, ie i == 0, then the total sum (j) should be 0.
    However I canot understand :
    for (int i = 1; i < n+1; i++) {
    dp[i][0] = true;
    }
    if we understand the design of dp[i][j] as whether the specifc sum j can be gotten from the first i numbers, then, dp[i][0] should mean whether the specific sum j == 0 can be gotten from the first i numbers where i in [1, n], which should be impossible, i.e false...

    Donno why they are set to true.Plz help! Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.