01背包 - [Algorithms, Dynamic program]

01背包问题：N个物品，一个最大承重W的背包，v【N】表示每件物品的价值，w【N】每一件物品的重量。

背包能装下的最大价值。

题目地址leetcode1143

分析：

使用一个数组dp【N】【W+1】表示状态，dp【i】【j】表示前i 件物品装入容量为j的背包中能取得的最大价值，

初始状态dp【0】【0.。。。W】使用第0件物品。。。

dp【0.。。N-1】【0】表示背包容量为0，此时价值均为0.

状态转移：

对于dp【i】【j】来说有两种情况

1. 第i件物品装入的话，dp【i】【j】 = dp【i-1】【j- w【i】】 + v【i】
2. 第i件物品不装入的话，dp【i】【j】 = dp【i-1】【j】

最后去两者中较大的值即可。

>for(int i=0;i<arr.length;i++){
   for(int j=0;j<capcity;j++){
       if( j >= arr[i]){
           dp[i][j] = Math.max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]);
       }else{
           dp[i][j] = dp[i-1][j];
       }
   }
>}

举个例子：

问题：

LeetCode416问题大概意思是：一个数组，能否平均的划分为两部分，使得每一部分的和一样。

>Input: [1, 5, 11, 5]
>Output: true
>Explanation: The array can be partitioned as [1, 5, 5] and [11].

思路：

将数组划分为两个子集，使得子集的和一样大，每一个数只能加入到其中一个集合中，其实是一个01背包问题，求一个集合使得，集合中所有元素的和为sum/2 ，开一个布尔数组dp【N】【Sum/2 + 1】，对于dp【i】【j】表示数组前i个数能否相加得到和为j，能为true，不能为false。

状态转移：

1. dp【i】【j】可能为：第i个元素加入集合，则dp【i-1】【j - arr【i】】
2. 不加入的话，可能为dp【i-1】【j】

最后1和2结果进行或运算。

解法：

>class Solution {
   public boolean canPartition(int[] nums) {
       int sum = 0;
       for(int i=0;i<nums.length;i++){
           sum += nums[i];
       }
       if(sum% 2 !=0) return false;
       int s = sum  / 2;
       boolean[][]  dp = new boolean[nums.length][s+1];//dp[i][j] 表示从前i个数中能否计算得到和为j
       for(int i=0;i<nums.length;i++){
           for(int j=0;j<=s;j++){
               if(i == 0){
                   if(nums[0] <= s){
                       dp[0][nums[0]] = true;
                   }
                   break;
               }
               if(j == 0){
                   dp[i][j] = false; 
               }
               if( j - nums[i] >=0){
                   dp[i][j] = dp[i-1][j - nums[i]] || dp[i-1][j];  
               }else{
                   dp[i][j] = dp[i-1][j];  
               }
           }
       }
       return dp[nums.length-1][s];
   }
   
>}