背包问题是一个组合优化的NP完全问题。问题可以描述为：给定一组物品，每个物品都有自己的重量和价格。在有限的总重量内，如何选择才能让物品总价最高？

目录

写在前面01背包问题，完全背包问题，多重背包问题，I多重背包问题，II为什么可以这样优化？一、二进制和十进制二。动态规划的时间复杂度估计。三。多背包分组背包问题。

写在前面

之前讲过简单的DP，经典的01背包问题，这里我就更深入的讲解一下背包问题，希望能帮助你更好的理解。

01背包问题

C语言数学题和简单DP01背包问题详解

先回忆一下这张图。

这里我再发一次01背包问题代码，可以用来对比。

二维：

#includebits/stdc。h

使用命名空间std

const int MAXN=1005

int v[MAXN]；//音量

int w[MAXN]；//值

int f[MAXN][MAXN]；//f [I] [J]，J卷下前I项的最大值

int main()

{

int n，m；

CIN nm；

for(int I=1；I=n；我)

cin五世w[I]；

for(int I=1；I=n；我)

for(int j=1；j=m；j)

{

//如果当前背包容量装不下第I个物品，则值等于第i-1个物品。

if(j v[i])

f[I][j]=f[I-1][j]；

//是的，你需要决定是否选择第I项。

其他

f[i][j]=max(f[i - 1][j]，f[I-1][j-v[I]]w[I])；

}

cout f[n][m]endl；

返回0；

}

一维：

#includebits/stdc。h

使用命名空间std

const int MAXN=1005

int f[MAXN]；//

int main()

{

int n，m；

CIN nm；

for(int I=1；I=n；i ) {

int v，w；

cin对w；//输入和处理。

for(int j=m；j=v；j -)

f[j]=max(f[j]，f[j-v]w)；

}

cout f[m]endl；

返回0；

}

完全背包问题

完全背包问题和01背包问题的区别在于，在完全背包问题中，每个物品都有无限个可用的棋子。我们也可以先尝试暴力写作。

#includeiostream

使用命名空间std

const int N=1010

int n，m；

int dp[N][N]，v[N]，w[N]；

int main(){

CIN nm；

for(int I=1；I=n；我)

cin五世w[I]；

for(int I=1；I=n；我)

for(int j=0；j=m；j)

for(int k=0；k * v[I]=j；K )//因为每件物品都有无限件可用，我们只需要找出价值最高的单品。

dp[i][j]=max(dp[i][j]，DP[I-1][j-k * v[I]]k * w[I])；

cout DP[n][m]endl；

}

优化理念：

让我们列出更新订单的内部关系：

f[i，j ]=max( f[i-1，j ]，f[i-1，j-v] w，f[i-1，j-2v] 2w，f[i-1，j-3v] 3w，…)

f[i，j-v]=max( f[i-1，j-v]，f[i-1，j-2v] w，f[i-1，j-3v] 2*w，…)

从上述两个公式中，可以得到下面的递推关系：

f[i][j]=max(f[i，j-v] w，f[i-1][j])

有了上面的关系，那么实际上可以消除K循环，核心代码优化成这样：

for(int I=1；I=n；我)

for(int j=0；j=m；j)

{

f[I][j]=f[I-1][j]；

如果(j-v[i]=0)

f[i][j]=max(f[i][j]，f[I][j-v[I]]w[I])；

}

这段代码很像01背包的非优化写法！我们来对比一下，下面是01背包的核心代码。

for(int I=1；I=n；我)

for(int j=0；j=m；j)

{

f[I][j]=f[I-1][j]；

如果(j-v[i]=0)

f[i][j]=max(f[i][j]，f[I-1][j-v[I]]w[I])；

}

这两个代码实际上只有一个区别(注意下标)

f[i][j]=max(f[i][j]，f[I-1][j-v[I]]w[I])；//01背包

f[i][j]=max(f[i][j]，f[I][j-v[I]]w[I])；//完全背包问题

因为和01背包代码很像，所以我们很容易想到进一步的优化。核心代码可以更改如下

for(int I=1；I=n；我)

for(int j=v[I]；j=m；J )//注意这里的J是从小到大枚举的，和01背包不一样。

{

f[j]=max(f[j]，f[j-v[I]]w[I])；

}

总结一下，一个完整的背包最后的写法如下：

#includeiostream

使用命名空间std

const int N=1010

int f[N]；

int v[N]，w[N]；

int main()

{

int n，m；

cinnm

for(int I=1；I=n；我)

{

cinv[I]w[I]；

}

for(int I=1；I=n；我)

for(int j=v[I]；j=m；j)

{

f[j]=max(f[j]，f[j-v[I]]w[I])；

}

coutf[m]endl；

}

多重背包问题 I

我们先来看看这个多重背包问题是不是和01背包问题很像。可以把sv和sw看成01背包问题吗？

for(ll I=1；I=n；我)

{

cinabc

for(ll j=1；j=c；j)

{

v[CNT]=a；

w[CNT]=b；

cnt

}//逐个移除多个背包

}

然后改装成01背包，解决问题。

#包含位/标准数据。h

使用命名空间std

typedef long long ll

const ll N=1e5 100

ll v[N]，w[N]；

ll f[N]；

int main()

{

ll n，m；

ll CNT=1；

cinnm

ll a，b，c；

for(ll I=1；I=n；我)

{

cinabc

for(ll j=1；j=c；j)

{

v[CNT]=a；

w[CNT]=b；

cnt

}//逐个移除多个背包

}

for(ll I=1；i=cnt我)

{

for(ll j=m；j=v[I]；j -)

{

f[j]=max(f[j]，f[j-v[I]]w[I])；

}

}//01背包

coutf[m]；

返回0；

}

多重背包问题 II

这个问题看起来和1没什么区别，只是数据范围变了。如果不优化，就会超时。如何优化？

我们只需要优化转化为01背包问题的部分。

int CNT=0；//重新分组项目后的顺序

for(int I=1；I=n；我)

{

int a，b，s；//a音量，b值，每一项的s数

scanf('%d %d %d '，a，b，s)；

int k=1；//二进制拆分装箱时，每组有K个同类物品。

While (k=s) //这就是Y一直说的：最后一组的项数是2(n ^ 1)1 2 4 8 16.2 n 2 (n 1)

{

cnt

v[CNT]=a * k；//每组的音量

w[CNT]=b * k；//每组的值

s-=k；

k *=2；//注意是k * 2，每次翻倍，不是K * K。

}

If (s 0) //二进制拆分后剩余的项数划分到新的组中。

{

cnt

v[CNT]=a * s；

w[CNT]=b * s；

}

}

为什么可以这样优化呢

我们知道任何数都可以转换成二进制数。二进制和十进制有什么区别？

一 、二进制与十进制

普通遍历问题

遍历n个条目，二进制计数法遍历的时间复杂度与十进制技术法遍历的时间复杂度相同。

例如，对于十进制数8

十进制遍历：0，1，2，3，4，5，6，7，共8次遍历。

二叉遍历：000，001，010，011，100，101，110，111，共8次遍历。

多重背包问题

同理，对于多背包问题，二叉遍历法也无法优化时间复杂度。

优化的原因是引入了动态编程。

二 、动态规划的时间复杂度估算

动态规划的时间复杂度问题总数要做的选择数。

比如01背包问题，问题总数为NV (n为物品数，v为背包容量)，要做的选择数为2(选或不选)。

那么01背包问题的时间复杂度大约是2NV.

三 、多重背包

如果不采用动态规划，就像普通的遍历问题一样，无论是否采用二进制计数法，都与时间复杂度的优化无关。

而二进制计数法会影响问题总数和问题选择数的乘积，即动态规划下多个背包的时间复杂度。

多背包动态规划的时间复杂度

十进遍历方法

问题总数是NV，n是物品数量，v是背包容量。

问题的选择数量大约是Smax，这是每一项的最大数量。

十进制多背包问题的DP时间复杂度为：NVSmax.

二叉遍历方法

在十进制中，一个项有si，在二进制中，就变成了1，2，…，lgsi项，于是就有了LG S1，LG S2 … LGSN项，大约Nlgsmax项。

问题总数是NVlgsmax.

问题的选择数量是2。

十进制多背包问题的DP时间复杂度为2 nvlgsmax。

最后看代码。

#包含位/标准数据。h

使用命名空间std

const int N=11 * 1000 10，M=2010

int v[N]，w[N]；

int f[M]；

int main()

{

int n，m；

scanf('%d %d '，n，m)；

int CNT=0；//重新分组项目后的顺序

for(int I=1；I=n；我)

{

int a，b，s；//a音量，b值，每一项的s数

scanf('%d %d %d '，a，b，s)；

int k=1；//二进制拆分装箱时，每组有K个同类物品。

While (k=s) //这就是Y一直说的：最后一组的项数是2(n ^ 1)1 2 4 8 16.2 n 2 (n 1)

{

cnt

v[CNT]=a * k；//每组的音量

w[CNT]=b * k；//每组的值

s-=k；

k *=2；//注意是k * 2，每次翻倍，不是K * K。

}

If (s 0) //二进制拆分后剩余的项数划分到新的组中。

{

cnt

v[CNT]=a * s；

w[CNT]=b * s；

}

}

n=cnt//所有组的数量就是01背包的物品数量。

//写01背包模板

for(int I=1；I=n；我)

for(int j=m；j=v[I]；j -)

f[j]=max(f[j]，f[j-v[I]]w[I])；

printf('%d '，f[m])；

返回0；

}

分组背包问题

地位：f[i][j]

集合：从前面第一组项目中选出的所有方案的集合，总体积不超过j .

属性：最大值

状态计算：

思想-集合的划分

分类依据：根据从I组中选择哪个项目。

f[i][j]=max(f[i][j]，f[I-1][j-v[I][k]]w[I][k])；

请看代码。

#includebits/stdc。h

使用命名空间std

const int N=110

int f[N][N]；//只选择前I组中的项目，当前音量小于等于j的最大值。

int v[N][N]，w[N][N]，s[N]；//v是体积，W是数值，S代表第I组的项目数。

int n，m，k；

int main(){

cinnm

for(int I=1；I=n；i ){

cins[I]；

for(int j=0；js[I]；j ){

cinv[I][j]w[I][j]；//读入

}

}

for(int I=1；I=n；i ){

for(int j=0；j=m；j ){

f[I][j]=f[I-1][j]；//如果不选择none，表示不选择I组中的所有项目，只选择I1组中的项目。

for(int k=0；ks[I]；k ){

if(j=v[I][k])f[I][j]=max(f[I][j]，f[I-1][j-v[I][k]]w[I][k])；

}

}

}

coutf[n][m]endl；

}

因为只使用了i-1列，所以可以按照01背包的套路反过来枚举体积。

#includebits/stdc。h

使用命名空间std

const int N=110

int f[N]；

int v[N][N]，w[N][N]，s[N]；

int n，m，k；

int main(){

cinnm

for(int I=0；在；i ){

cins[I]；

for(int j=0；js[I]；j ){

cinv[I][j]w[I][j]；

}

}

for(int I=0；在；i ){

for(int j=m；j=0；j - ){

for(int k=0；ks[I]；k){//for(int k=s[I]；k=1；K-)没关系。

if(j=v[i][k]) f[j]=max(f[j]，f[j-v[I][k]]w[I][k])；

}

}

}

coutf[m]endl；

}

关于C语言动态编程中各种背包问题的分析和讲解，本文到此为止。更多关于C语言背包问题的信息，请搜索我们之前的文章或者继续浏览下面的相关文章。希望大家以后能多多支持我们！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。