一、01背包问题01背包顾名思义是0不带，1不带，而且一次只能装一件物品在背包里。
两种方法是打开1.2维数组打开2.1维数组
1.开二维数组的状态方程：
该方案设想将行李放入一定容量的背包，使包内的行李达到最大价值
这个博客写道，他非常理解https://blog.csdn.net/weixin _ 43828245/article/details/86622480
for(I=1； i=n； I ) for(j=1； j=weight； j () if ) m[I]j ) sum[i][j]=sum[i-1][j]； else//可以安装{ sum [ I ] [ j ]=max (sum [ I-1 ] [ j-p [ I ] ] m [ I ]，sum[i-1][j] )； //比较戴和不戴的最大价值}}printf('%dn”，sum[n][weight] )；实际上就是在每个物品的基础上，遍历所有可能的背包空间，如果放得下去就比较放与不放对价值的影响
2.开一维数组状态方程：
如果剩下的容量可以装这个东西，有两种情况。 要么放进去要么放不进去。
选择安装后，sum[j]=sum[j-m[i]] p[i]；
如果不安装，则sum[j]=sum[j]；
最终结果采用两种情况的最大值。
sum[j]=max(sum[j],sum[j-m[i]]+p[i]);
(sum[j]表示容量不超过j时的最大价值)
转换为代码：
for(intI=0； in； I ) for(intj=Weight； j=0； j--{if=m[I]}sum[j]=max[j]，sum[j-m[i]] p[i]； }printf('%dn '，sum[weight] )； 这里需要注意的是，01背包的一维排列在更新时显示为相反的顺序。 从代码中可以看出，一个值的更新是根据该值左边的值进行更新的。 逐次更新的情况下，更新时一定会先更新左边的值，所以之后更新的值有可能是基础性更新，但是如果是逆序更新的话就可以避免这个问题。 之所以这么说，是因为01背包只能放一次各个物品，所以如果顺序被更新的话，假设状态1已经有一个物品，那么基于状态1的状态2在需要更新的时候，不是会放入两个物品吗？ 这将导致错误，因此应该需要反向更新。 (该段文本转载于https://blog.csdn.net/weixin _ 43849505/article/details/89423390 )
相关例题如下所示。
A -高频Umaru系列(9) ——西伯利亚雪橇犬
二维码：
# include stdio.h # include stdlib.h # include string.hint main ({ intn，x，I，j； int p[101]，m[101]； int sum[101][1001]={0}； while((scanf ) (%d%d )，n，x ) ) for ) ) I=1； i=n； I ) scanf('%d%d )、p ) I )、m ) I )； for(I=1； i=n； I ) for(j=1； j=x； j () if ) p[I]j ) /手头剩下的钱不够买sum[i][j]=sum[i-1][j]。 else//黄金足够买{ int a1=sum[i-1][j-p[i]] m[i]； int a2=sum[i-1][j]； //if(a1a2) sum[i][j]=a1； else sum[i][j]=a2； }}printf('%dn '，sum[n][x]； } return 0； }一维交流码：
# include stdio.h # include stdlib.h # include string.hint max (inta，int b ) { return ab？ a:b； (}int main ) ) { int n，x，I，j； int p[101]，m[101]； wile((Scanf ) (%d%d )，n，x ) ) { int sum[10001]={0}； for(I=0； in； I ) scanf('%d%d )、p ) I )、m ) I )； for(I=0； in； I(//各西伯利亚哈士奇(for ) j=x； j=0； (j ) ) ) /遍历剩下的每一张钱) if(j=p[I] ) /现在剩下的钱是这个西伯利亚哈士奇sum[j]=max ) sum[j]，sum[j-p[I] }printf('%dn”，sum[x] )； } return 0； (二)完全背包问题与01背包问题有共通之处，不同的是01不能放多个同种的，而完全背包可以放多个同种的。
正如前面01背包一次元化的故事中所说的那样，逆序更新是防止放入两个，所以这里完全背包利用了它。 01将背包的逆序更新置换为顺序更新，可以解决放入几个的问题。 更新所有还可以放入的状态，从左到右更新。 如果当前状态再进入一个，则可以再进入基于该状态的另一个状态。 (该段文本转载于https://blog.csdn.net/weixin _ 43849505/article/details/89423390 )
转换为代码：
for(intI=0； in； I ) for(intj=0； j=weight； j ) (if ) j=m[I] ) sum ) j )=max ) sum[j]，sum[j-m[I] ) p[I] )； }printf('%dn '，sum[weight] )； 例题：
输入输出示例：
交流电源线：
# include stdio.h # include stdlib.h # include string.hint max (inta，int b ) { return ab？ a:b； (}int main ) ) { int n，I，j，x，k； ints [3]={ 150，200，350 }； scanf('%d '，n )； int sum[10001]； for(k=0； kn； k ) scanf('%d '，x )； memset(sum，0，sizeof ) sum )； for(I=0； i3； I ) for(j=0； j=x； j(/顺序更新(if ) j=s[I] ) sum ) j )=max ) sum[j]，sum[j-s[I]s ) /比较) %dn '，} return 0； }