image.png

分析

完全填满背包
F(n,c)这里表示使用n个物品能否将容量为C的背包填满，这里是个布尔值
image.png
或者用i-1个物品填满背包(此时不用第i个物品),或者用i-1个物品填满c-w(i)的物品(此时可以用w(i)去填满)

code

记忆化搜索

  1. class Solution {
  2.     //memo[i][c]表示使用索引为[0...i]的这些元素，是否可以完全填充一个容量为c的背包
  3.     //-1表示未计算，0表示不可以填充，1表示可以填充
  4.     private int[][] memo;
  5.     public boolean canPartition(int[] nums) {
  6.         int sum = 0;
  7.         for(int i:nums)
  8.             sum+=i;
  9.         if(sum%2!=0)
  10.             return false;
  11.         memo = new int[nums.length][sum/2+1];
  12.         for(int i=0;i<nums.length;i++)
  13.             Arrays.fill(memo[i],-1);
  14.         return tryPartition(nums,nums.length-1,sum/2);
  15.     }
  17.     //使用nums[0....index],是否可以完全填充一个容量为sum的背包
  18.     private boolean tryPartition(int[] nums,int index,int sum){
  19.         if(sum==0)
  20.             return true;
  21.         if(sum<0||index<0)
  22.             return false;
  23.         if(memo[index][sum]!=-1)
  24.             return memo[index][sum]==1;
  25.         memo[index][sum] =  (tryPartition(nums,index-1,sum)||tryPartition(nums,index-1,sum-nums[index]))?1:0;
  26.         return memo[index][sum] == 1;
  27.     }
  28. }

动态规划

  1. class Solution {
  3.     public boolean canPartition(int[] nums) {
  4.         int sum = 0;
  5.         for(int i:nums)
  6.             sum+=i;
  7.         if(sum%2!=0)
  8.             return false;
  9.         int n = nums.length;
  10.         int C = sum/2;
  11.         boolean[] memo = new boolean[C+1];
  13.         for(int i=0;i<=C;i++)
  14.             memo[i]=(nums[0]==i);
  17.         for(int i=1;i<n;i++)
  18.             for(int j=C;j>=nums[i];j--)
  19.                 memo[j]=memo[j]||memo[j-nums[i]];
  20.         return memo[C];
  21.     }