0-1背包问题（一）

系列文章目录

0-1背包问题（一）

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：以下是本篇文章正文内容，下面案例可供参考

一、0-1背包问题是什么？

背包问题是「动态规划」中十分经典的一类问题，背包问题本质上属于组合优化的「NP 完全问题」。因为组合数量过多，因此无法通过穷举法来解决问题，这就是为什么「背包问题」会使用「动态规划」来求解的根本原因。下面通过简单示例来讲述0-1背包问题。

二、分割等和子集（Leetcode 416中等）

1.问题描述

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

2.算法概述

2.1 0-1背包问题问题的基本思路

0-1背包问题本质上还是动态规划问题，动态规划的问题的本质在于寻找下一个状态和上个状态的变化带来的数值变化，即状态转移方程，dp[i][j]和dp[i-1][j]之间的关系。
0-1背包问题其实也是同样的问题，dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]),意思就是每次遍历到一个物品，都有两个选择：取或者不取，取了背包的容积就会减少，不取则保持原来的状态。

2.2 具体问题分析

此题可以转换为背包问题，问题建模过程：背包的容积有多大、物品的数量和价值、结果形式

1.物品的数量：nums的size
2.物品的价值：nums对应的数值
3.背包的容积：这个是一般形如背包问题的难点，此处题中并没有明说背包最大值是多少，此时需要把问题变形：使两个子集的元素和相等==》每个子集的和==所有元素和的1/2，因此背包的容积也显而易见即所有元素和的1/2。
4.结果形式：首先得分析我们计算出来的结果是什么，计算获得的值为以此为背包容积所能获得的最大值，问题是能否相等，因此结果的形式就可以转换为：背包能否被装满，即最大值是否等于背包的容积。
本文只介绍最原始的背包问题解法，这也是最初的形式，后面几篇都会围绕该题做出多种变种和优化

2.4 代码展示：

class Solution {
    
public:
    bool canPartition(vector<int>& nums) {
    
        int N=nums.size();
        int sum=0;
        for(int i=0;i<N;i++)
        {
    
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int C=sum/2;
        vector<vector<int>>dp(N,vector<int>(C+1,0));
        // 先处理「考虑第一件物品」的情况
        for (int i = 0; i <= C; i++) {
    
            dp[0][i] = i>=nums[0] ? nums[0] : 0;
        }
        // 再处理「考虑其余物品」的情况
        for (int i = 1; i < N; i++) {
    
            for (int j = 0; j < C + 1; j++) {
    
                // 不选该物品
                int n = dp[i - 1][j];
                // 选择该物品，前提「剩余容量」大于等于「物品体积」
                int y =j>nums[i]? dp[i - 1][j-nums[i]]+nums[i]:0; 
                dp[i][j] =max(n,y);
            }
        }
        return dp[N-1][C]==C;
}
};

总结

提示：这里对文章进行总结：
今天主要讲解了「什么是背包问题」、「背包问题的本质是什么」以及「为什么背包问题需要用到动态规划来求解以及背包的解决套路和变形题的难点，其中「01背包」问题是众多背包问题中核心。