01背包问题(01背包问题图解)

通过入门系列-路径题目，我们掌握了DP四步走和滚动阵列的核心思想。

现在，我们正在进入背包问题，它是最大和最多样化的DP问题。

代表性的背包容器可以是楼梯数、账户总额和包裹容量。

通常情况下，一个项目有一个或两个属性的价值和数量。根据条目，题目可根据选择次数细分为01、完整、多重(一次、不限次数、不同条目不同次数)。

思维分析:

我选择了前几个项目。

j背包的当前容量

DP[i][j]选择前几项填充当前容量所能获得的最大值。

等式转换选择或不选择最大值。

DP[i][j] = Max(DP[i-1][j]，DP[I-1][j-w[I]]+v[I])；

边界DP [0] [k] = k >: = w[0]？v[0]:0；

类求解{public int max value (int n，int c，int [] v，int[]w){//注意:这里初始化的一维是n，二维是C+1。最后，大小DP[n-1][c]int[]DP = new int[n][c+1]取决于endCase下标。//当只考虑第一项时，baseCase首先处理每个容量的最大值(int j = 0；j & lt= C；++){//背包容量大于第一件物品容量才能放进去，最大值为第一件物品的值，否则为0dp[0][j]= j >；= w[0]？v[0]:0；}//对于(int i = 1，重新处理“考虑其余项”的情况(因为有多个项可以选择也可以不选择，多个结果的最大值不一样)；我& ltn；i++){ for(int j = 0；j & ltc+1；++){//不选择此项int n = DP[I-1][j]；//选择此项，前提是其容量可以填充当前背包容量int y = j >；= w[i]？DP[I-1][j-w[I]]+v[I]:0；dp[i][j] = Math.max(n，y)；} }//为什么不是[N-1][C-1]？因为二维下标参与计算有实际意义，需要达到C返回DP[N-1][C]；}}空优化-滚动数组

dp转移的时候，一个维度一次只需要一级，可以用滚动数组。

需要二维J，j-w[i]，即每次都需要采集当前上栏和左栏的数据。

此时通过调整两个维度的遍历方向，从后向前计算DP[j]时，最后的DP[j]和DP[j-w[i]]还没有被覆盖。

即l，r然后DP[j] = max(l，r)

class Solution { public int max value(int N，int C，int[] v，int[]w){ int[]DP = new int[C+1]；for(int I = 0；我& ltn；i++){ for(int j = C；j & gt= v[I]；j-){//不选择此项int n = DP[j]；//Select this item int y = DP[j-v[I]]+w[I]；dp[j] = Math.max(n，y)；} } return DP[C]；}}}知道了01背包处理框架，接下来我们要学习如何拥有背包建模能力，即将问题转化为背包问题。

问题相当于“能否从数组中选取几个元素，使得元素之和等于所有元素之和的一半”。

如果把这个问题抽象为“背包问题”，应该是:

我们的背包容量是，每个数组元素的“值”和“代价”就是它的数值。请询问我们是否能装满背包。

直接一维解

class Solution { public boolean can partition(int[]nums){ int n = nums . length；//等和子集的和必须是总数的一半。int sum = 0；for(int I:nums)sum+= I；int target = sum/2；//对应和为奇数的情况，注定不会被分成两个“等和子集”if (target * 2！= sum)返回false//取消“项目维度”int[]f = new int[target+1]；for(int I = 0；我& ltn；i++){ int t = nums[I]；//将“容量维度”更改为从大到小遍历for(int j = target；j & gt= 0;j-){//不选第I项int no = f[j]；//选择第I项int yes = j >；= t？f[j-t]+t:0；f[j] = Math.max(否，是)；} }//如果最大值等于target，则意味着可以拆分成两个“等和子集”返回f[target]= = target；}}如何培养问题抽象的能力？首先需要积累一定的刷题量，总结转化的要点。

比如这个话题转换的关键点就是我们需要把“划分等和子集”等同于“选择一个数组中的一些元素，使它们的和是总数的一半”

但这个问题有一个“小问题”:最后通过“判断”得出答案。

通过确定获得的最大值是否等于target来确定“等和子集”是否可以被划分。

虽然逻辑上成立，但总给我们一种“间接解决”的感觉。

这主要是因为我们没有对“01背包”的“状态定义”和“初始化”做任何改动。

但实际上我们可以稍微改变一下“01背包”的思路来进行“直接求解”

以及参数返回值:boolean DP[i][j]:选择第I个元素，数字之和是否为j。

转移公式:

基本情况:想当然地认为fn[0][nums[0]]必须为真，但不是，如果nums[0]>:它是target fasle

我们重新定义I为0为不选择，I为1为选择第一个，这样fn[0][0] = true表示不选择任何东西。容量必须为0，并且始终为真。

可以看出，我们在这里重新定义了参数I、返回值、transfer和baseCase，以获得直接解。

直接从上一个维度优化答案空

class Solution { public boolean can partition(int[]nums){ int n = nums . length；//等和子集的和必须是总数的一半。int sum = 0；for(int I:nums)sum+= I；int target = sum/2；//对应和为奇数的情况，注定不会被分成两个“等和子集”if (target * 2！= sum)返回false//取消“项目维度”boolean[]f = new boolean[target+1]；f[0] =真；for(int I = 1；我& lt= n；i++){ int t = nums[I-1]；for(int j = target；j & gt= 0;j-){//不选择此项boolean no = f[j]；//选择此项boolean yes = j >；= t？f[j-t]:假；f[j] =否|是；} } return f[目标]；}}}总结思考恢复磁盘DP的四个步骤I，J代表什么数组返回值是什么转移公式baseCase

01我背包前的物品。填充量为J的背包返回最大值。

当前项是否选中DP [I] [J] = Max (DP [I-1] [J]，DP[I-1][J-W[I]+V[I]])；

循环DP [0] [k] = k >: = w[0]的基本情况？v[0]:0；

伪代码:

int[][]fn = new int[N][C+1]；

对于(i 1 - N-1) {

对于(j 0 - C) {

n = DP[i-1]

m = j & gt= w[i]？DP[I-1][j-w[I]+v[I]]:0；

fn[i][j] = max(m，n)

}

}

return fn[N-1][C]；

滚动数组&1，将空之间的间隔减少到O(2N)

一维空优化将空减少到O(N)。一维优化思想是后续完全背包问题降维的核心。

根据公式，DP [I] [j] = max (DP [I-1] [j]，DP[I-1][j-w[I]+v[I])；

也就是每次需要前一行的当前位置和左边的一个位置，就从大到小遍历(保证前一个元素还是最后一个结果)。

int[]fn = new int[C+1]；

对于(i 1 - N-1) {

for (j C - w[i]) {

n = fn[j]；

m = fn[j-w[i]]+v[i]

}

}

return fn[C]；

很多DP问题并不直观，我们需要学会将其转化为一些背包问题，比如416分割和子集。

找出数组中是否有任何元素可以组合成一个和。一半的元素只能使用一次。

奇数直接返回false。

W[] v[]是nums[]

补能力目标，其值正是目标。last = =比较返回true或false。

N = nums .长度

c = sum/2；

int[]fn = new int[C+1]；

对于(i 1 - N-1) {

for (j C - nums[i]) {

n = fn[j]；

m = fn[j-nums[i]]+nums[i]

fn[j] =最大值(n，m)

}

}

返回fn[目标] ==目标

是不是很直观？感觉是间接解决，可以改变01背包的思路。

DP[i][j]返回查找Max是否可以等于target(布尔值)

j的含义保持不变，返回变成boolean。

DP[I][j]= DP[I-1][j]| | DP[I-1][j-w[I]]

当baseCase DP[0][nums[0]]被选为第一项时，其值必须等于nums[0]，即DP[0][nums[0]] = true。

看起来没问题，但是nums[0]必须< = target在迭代范围内，所以做不到。

那么只有当该项未被选中时，其值必须从0改为I，并定义DP[0][0] = true。

boolean[] fn =新布尔值[C+1]；

fn[0] =真

对于(i 1 - N) {

for (j C - nums[i-1]) {

n = fn[j]；

m = fn[j-nums[i-1]]

fn[j] = m || n

}

}

返回fn[目标]