背包问题（用到动态规划）

作者:神秘网友 发布时间:2020-10-12 13:12:56

背包问题（用到动态规划）

背包问题（用到动态规划） 
给定一个只包含正整数的非空数组。
是否可以将这个数组分割成两个子集，
使得两个子集的元素和相等。

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
0到i中一些数和为j
0到i-1中一些数和为j
0到i-1中一些数和为j - nums[i] （此时选择nums[i] 和也就是j了）
目的还是和为j

背包问题：
列一个二维表格来理解

背包问题（用到动态规划）
dp[1][6]能为true的关键是因为

0到i-1中一些数和为j - nums[i] 
（此时选择nums[i] 和也就是j了）
目的还是和为j
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
此时dp[1][6] = dp[0][6] || dp[0][6-nums[1]];
//此时后面这个为true

dp[0][0]为true的合理性

本来容量为0的时候，应该考虑设置为false
但由于
 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
 j - nums[i]等于0时，j=nums[i]，说明nums[i可以被单独分为一组

竖代表实际值的大小
横代表背包的实际容量

最后一个元素是5

T代表的是目前的背包容量的值可以有之前的实际值组合而成

代码：

public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 特判：如果是奇数，就不符合要求
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        // 再填表格后面几行
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                // 直接从上一行先把结果抄下来，然后再修正
                dp[i][j] = dp[i - 1][j];

                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
           
                }
            }
        }
        return dp[len - 1][target];
    }
}


还可继续优化
我们采用的二维数组，实际上，每一行的元素是根据上一行得出来的
变成一位数组即完成了优化

代码如下：

public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = target; nums[i] <= j; j--) {
                if (dp[target]) {
                    return true;
                }
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

背包问题（用到动态规划）相关教程

  1. 解决Github连接缓慢图裂问题

    解决Github连接缓慢、图裂问题 1.通过修改本地hosts文件加速github 1.1 手动修改更新 首先我们需要找到自己设备上的hosts文件，不同的平台其存放路径各不相同，主要的平台hosts文件所在路径如下： Windows ：C:\Windows\System32\drivers\etc\hosts Linux：/

  2. virtulbox安装win7的过程和碰到的一些问题

    virtulbox安装win7的过程和碰到的一些问题 软件开发工作基本结束，需要测试软件的运行环境，由于用户的计算机没有更新太快，使用win7系统的较多，我们需要在win7环境下，使用不同的浏览器测试软件运行情况。使用的方法就是利用virtualbox安装win7虚机测试。

  3. 解决同步验证码模拟登录问题

    解决同步验证码模拟登录问题 1、如何识别验证码 前言：识别验证码借助第三方库很好识别，主要是获得验证码识别后又相当一次request请求，这就会导致与当前页面的验证码不同，即使成功识别也会因为验证码的不统一而登录不了 通过selenium自动化测试工具自动定

  4. OSS对象存储的文件追加上传问题及解决方案

    OSS对象存储的文件追加上传问题及解决方案 最近项目中碰到这样一个问题，在我们软件的版本更新中的更新日志，需要每次更新的内容对同一个文件进行追加。然后我看了下阿里云的文档是这样写的，地址https://help.aliyun.com/document_detail/84784.html?spm=a2c

  5. 关于printf()输出浮点数保留小数问题

    关于printf()输出浮点数保留小数问题 printf()输出浮点数保留小数问题 #include stdio.hint main(void){ float a = 0.205, b = 0.215, c = 0.225, d = 0.235, e = 0.245; float f = 0.255, g = 0.265, h = 0.275, i = 0.285, j = 0.295; printf(\n); printf(%

  6. 解决IDEA中Vue项目出现红色波浪线问题

    解决IDEA中Vue项目出现红色波浪线问题 明天上班要用vue.js，今天周日，学一下明天用，遇到一个小问题记录一下，如下图： 话不多说，直接上菜，照着图设置就完了： 结果： 结语： 理论上应该是不影响使用，但有个红色波浪线，我想在座的各位应该是容忍不了的

  7. 解决VMware克隆Linux无法上网问题

    解决VMware克隆Linux无法上网问题 在实验过程中 linux 系统不够使用，怎么办？难道我们一五一十的重新安装 linux 系统？当然不是，我们可以使用虚拟机上面克隆功能，克隆出另外一个 linux 系统，减少了重头安装 lnux 消耗的时间。克隆过去的 linux 系统就可

  8. 友盟推送通知栏问题

    友盟推送通知栏问题 在使用友盟推送的过程中，由于升级了推送sdk，推送的时候log能够打印出推送的消息，但是通知栏不会弹出，这个问题找了好久都没找到原因，代码又不能找到之前的版本。 这是我升级到的最新SDK //基础组件库依赖(必须) implementation 'com.u