算法训练营Day43(背包问题）

?1049.?最后一块石头的重量?II?

1049. 最后一块石头的重量 II - 力扣（LeetCode）

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int num:stones){
            sum+=num;
        }
        int target = sum/2;
        //1 dp数组：背包容量为j，所背的最大价值为dp[j]{也就是最大重量}
        int [] dp = new int[target+1];

        //3初始化 都是0，

        //4b遍历顺序 先物品，-再背包
        for(int i = 0;i<stones.length;i++){
            for(int j = target;j>=stones[i];j--){
                //2递推公式
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        //一堆石头是dp[target] 另一堆是sum-dp[target]
        return sum-dp[target]-dp[target];

    }
}

494.?目标和?

494. 目标和 - 力扣（LeetCode）

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
    	//如果target过大 sum将无法满足
        
        if ( target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        //1 dp数组: 装满容量为j的背包，有dp[j]种方法
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}

474.一和零??

474. 一和零 - 力扣（LeetCode）

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //1 pd数组，i表示m j标识n   dp[i][j] 表示最多能装多少个物品
        int [][] dp = new int [m+1][n+1];
        //3 正常的初始化 第一个数组是递推公式+1得到的
        dp[0][0] = 0;
        //当前字符串0 1 的个数
        int x,y;
        //4遍历顺序
        for(String str : strs){//遍历物品
            x = 0;
            y = 0;
            for(char ch : str.toCharArray()){
                if(ch=='0'){
                    x++;
                }else{
                    y++;
                }
            }
            //遍历背包
            for(int i = m;i>=x;i--){
                for(int j = n;j>=y;j--){
                    //2递推公式
                    //dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
                    dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);
                }
            }
        }
        return dp[m][n];        
        
    }
}