0-1背包问题

0-1背包问题：
一个可装载W重量与N个物品的背包，每一个物品都有重量与价值两个属性，求当前背包可装载的最大价值是多少。

状态与选择
状态有两个： 背包的容量与可选择的物品
选择： 装进背包或者不装进背包

动态规划框架
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for...
dp[状态1][状态2][...] = 求最值（选择1，选择2...）

dp[i][w] 对于前i个物品，背包容量为w时所对应的装载最大价值。
dp[3][5] 为对于前3个物品，当背包容量为5时对应的最大装载价值。

细化框架

int[][] dp= new int[N+1][W+1];
dp[0][] = 0;
dp[][0] = 0;
for i个物品 in N个物品:
    for j重量 in W重量:
        dp[i][j] = max[物品i放进背包，物品j不放进背包]

当物品放进背包，dp[i][j] = dp[i-1][W-w[i]] + i的价值


给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
 
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.


1.求和为sum。即为两个背包装sum/2的重量，每一个数只能使用一次
2.dp[i][j]表示前i个数是否可以装满j
3.dp[i][j] = dp[i-1][j] 表示不装进背包
  dp[i][j] = dp[i-1][j-nums[i]] 表示装进背包

public boolean canPartition(int[] nums) {
//dp[i][j]表示i个元素和是否可以是j 是则为true 否则为false
int sum = 0,target = 0;
for (int i = 0; i < nums.length; i++){
sum = sum + nums[i];
}
if (sum %2 == 1){
return false;
}else{
target = sum /2;
}
boolean[][] dp = new boolean[nums.length+1][target+1];
//初始状态为false
for (int i = 0;i < dp.length; i++){
Arrays.fill(dp[i],false);
}
//当j为0时，可以选择不将元素装入背包中
for(int i = 0; i < dp.length;i++){
dp[i][0] = true;
}
for (int i = 1; i < dp.length; i++){
for (int j = 1;j <= target;j++){
if (j < nums[i-1]){
//背包容量不足,不能将该值放入背包
dp[i][j] = dp[i-1][j];
}else {
//背包容量满足,选择放入背包中dp[i][j] = dp[i-1][j-nums[i-1]]
//不放入背包或上放入背包
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
}
return dp[nums.length][target];
}