本文主要介绍了C语言动态规划中背包问题的详细说明。通过示例代码进行了非常详细的介绍，对大家的学习或工作都有一定的参考价值。有需要的朋友下面和边肖一起学习。
01背包问题
给定n种物品和一个容量为C的背包，物品I的重量为w[i]，价值为v[i]。问：如何选择装入背包的物品，使背包的总价值最大化？(面对每一个武平，你只能选择拿还是不拿。不能选择加载一个物品的一部分，也不能多次加载一个物品。)
声明一个数组f[n][c]的二维数组，其中f[i][j]表示面对第I个物品时可以获得的最大值，背包容量为j。
根据题目要求，通过打表的方式查找相关的边界和规律。
根据列表写出相关的状态转移方程。
状态转移方程的程序实现
真题演练：
一个旅行者有一个最多能装100公斤的背包.现在有N个项目，它们的权重是W1，W2，W3，W4，…，Wn。它们的价值分别是C1、C3、C2、…、Cn，让旅行者获得最大价值。
输入描述：
第一行：两个整数，M(背包容量，M=200)和N(物品数量，N=30)；
第2行…N 1:每行两个整数Wi，Ci，表示每件物品的质量和价值。
输出描述：
只有一行，一个数字，表示最大总价值。
样例：
输入：
10 4
2 1
3 3
4 5
7 9
输出：
12
解题步骤
定义一个数组dp[i][j]来表示当容量为j时取第I项可以得到的最大值。
根据题目要求打表，列出对应的dp表。
质量
五[一](价值)
0
一个
2
三
四
五
六
七
八
九
10
0
0
0
0
0
0
0
0
0
0
0
2
一个
0
0
一个
一个
一个
一个
一个
一个
一个
一个
一个
三
三
0
0
一个
三
三
四
四
四
四
四
四
四
五
0
0
一个
三
五
五
六
八
八
九
九
七
九
0
0
一个
三
五
五
六
九
九
10
12
对于一个动态规划问题，设置下标最好从0开始，因为动态规划往往和之前的状态有关！从上面的dp表可以看出，判断我们能不能拿一个物品需要两步。第一步：判断背包当前的容量j是否大于物品当前的质量，如果物品的质量大于背包的容量那么就舍弃。第二步：如果背包可以装下这个物品，就需要判断装下该物品获取的最大价值是不是大于不装下这个物品所获取的最大价值，如果大于那么就把东西装下!根据这个想法，我们可以得到状态转移方程：
如果单签背包的容量可以装物品：
dp[i][j]=max(dp[i-1][j]，DP[I-1][j-w[I]]v[I])；
如果当前背包容量容纳不下物品：
DP[I][j]=DP[I-1][j]；
#包含stdio.h
int max(常量int a，常量int b)
{
还ab？甲：乙；
}
int main()
{
int w[35]={0}，v[35]={0}，DP[35][210]={ 0 }；
int n，m；
scanf('%d %d '，m，n)；
int i，j；
for(I=1；I=n；i ){
scanf('%d %d '，w[i]，v[I])；
}
for(I=1；I=n；i ){
for(j=1；j=m；j ){
If(j=w[i])//如果当前背包的容量大于商品的质量
{
dp[i][j]=max(dp[i-1][j]，DP[I-1][j-w[I]]v[I])；//判断是否应该赢
}
否则//大于背包的当前容量
{
DP[I][j]=DP[I-1][j]；
}
}
}
for(int k=0；k=n；k)
{
for(int l=0；l=m；l)
{
printf('%d '，DP[k][l])；
}
printf(' \ n ')；
}
printf('%d\n '，DP[n][m])；
}
通过运行上面的程序，我们可以看到最终输出的dp表符合我们的预期！但是还没完，动态规划有一个后无效性原则(当前状态只与前一个状态有关)。然后我们可以压缩dp数组，把二维数组转换成一维数组。每次选择一个项目时更新这个数组！那么状态转移方程就可以压缩成dp[j]=max(dp[j]，dp[j-w[i]] v[i])。但是，我们需要注意在压缩过后我们需要逆序刷新数组的值。如果刷新正序列，则不能保存前一阶段获得的最大值对应的值。然后我们可以编写下面的程序：
#包含stdio.h
int max(常量int a，常量int b)
{
还ab？甲：乙；
}
int main()
{
int w[35]={0}，v[35]={0}，DP[210]={ 0 }；
int n，m；
scanf('%d %d '，m，n)；
int i，j；
for(I=1；I=n；i ){
scanf('%d %d '，w[i]，v[I])；
}
for(I=1；I=n；i ){
for(j=m；j=0；j - ){
If(j=w[i])//如果当前背包的容量大于商品的质量
{
dp[j]=max(dp[j]，DP[j-w[I]]v[I])；//判断是否应该赢
}
}
for(int k=0；k=m；k)
{
printf('%d '，DP[k])；
}
printf(' \ n ')；
}
printf('%d\n '，DP[n][m])；
}
可以看出和上面的dp表输出没什么区别！
完全背包问题
题目描述：
有n种物品，每种物品都有一个重量和一个数值，但是每种物品的数量是无限的。有一个背包，最大载重量为M，现在从N中选取若干物品(同一物品可多次选取)，使其质量小于等于M，取值之和最大。
输入：
第一行：两个整数，M(背包容量，M=200)和N(物品数量，N=30)；
第2行…N 1:每行两个整数Wi，Ci，表示每件物品的质量和价值。
输出：
只有一行，一个数字，表示最大总价值。
样例：
输入：
10 4
2 1
3 3
4 5
7 9
输出：
12
和01背包问题不同的是，它不是每个物品带不带的问题，而是选择几个物品，最后选择价值最大的一个。那么我们可以在01背包上继续思考这个问题。在01背包里，我们知道了之前的状态，我只要判断要不要拿K物品，和没拿的对比就行了。如果价值比以前更大，我会买下它们。而且每种最多只能带j/w[i]个物品，所以加个重循环就行了！该程序的核心代码如下：
for(I=1；I=n；i ){
for(j=m；j=0；j - ){
for(k=0；k=j/w[I]；k)
{
dp[j]=max(dp[j]，DP[j-k * w[I]]k * v[I])；//确定是否应该赢K项。
}
}
}
通过代码可以发现，这个简单的算法需要三重循环，看起来时间复杂度很高。然后我们也借鉴01背包观看完整的背包！
质量
五[一](价值)
0
一个
2
三
四
五
六
七
八
九
10
0
0
0
0
0
0
0
0
0
0
0
2
一个
0
0
一个
一个
2
2
三
三
四
四
五
三
三
0
0
一个
三
三
四
六
六
七
九
九
四
五
0
0
一个
三
五
五
六
八
10
10
11
七
九
0
0
一个
三
五
五
六
九
10
10
12
根据表中红色标注的数值，需要注意的是，如果背包的容量装不下目前物品的质量。那么当前容量所能容纳的最有价值的物品就等于最后一个物品所能容纳的最大值。重点说说4是怎么来的。这个4不是从i-1来的，而是从I来的，用正序推导出该项的值。状态转移方程可以写成：DP [I] [J]=max (DP [I-1] [J]，DP [I] [J-W [I]] V [I])和背包01唯一的区别就是max的第二个参数。01背包是i-1，而完全背包是I，是正序推理得到的状态转移方程。
根据状态转移方程，程序应该快写好了！但是根据dp的后失效原理，动态规划的状态转移方程是压缩的！压缩后为dp[j]=max(dp[j]，dp[j-w[i]] v[i])。来看看是不是和01背包的状态转移方程一模一样，朋友们！但两者有一个显著的区别：01背包使用的是前一个的数据，因此需要进行反转，以避免覆盖之前的值，而完整的背包则是从当前更新的数据进行相关操作。通过以上分析，我们可以编写以下程序：
#包含stdio.h
int max(常量int a，常量int b)
{
还ab？甲：乙；
}
int main()
{
int w[35]={0}，v[35]={0}，DP[210]={ 0 }；
int n，m；
scanf('%d %d '，m，n)；
int i，j；
for(I=1；I=n；i ){
scanf('%d %d '，w[i]，v[I])；
}
for(I=1；I=n；i ){
for(j=0；j=m；j ){
If(j=w[i])//如果当前背包的容量大于商品的质量
{
dp[j]=max(dp[j]，DP[j-w[I]]v[I])；//判断是否应该赢
}
}
for(int k=0；k=m；k)
{
printf('%d '，DP[k])；
}
printf(' \ n ')；
}
printf('%d\n '，DP[m])；
}
从上面代码的输出可以看出，打印出来的dp表和我们推测的没有区别，程序是正确的！
多重背包问题
题目描述：
为了庆祝班级在校运会上获得第一名，班主任决定举办庆功宴，并拨款为运动员购买奖品。预计分配的金额可以买到最大价值的奖品，可以补充自己的精力和体力。
输入：
在第一行中，输入两个数字N (N=500)和M (M=6000)，其中N代表要购买的奖品数量，M代表分配的资金数量。
接下来的n行，每行3个数字，W、V、s V、S分别代表I奖的价格、价值(价格和价值是不同的概念)以及可以购买的最大数量(可以买0块到S块)，其中W=100，V=1000，S=10
输出：
Line:一个数字，表示你这次购买可以获得的最大价值(注意！不是价格)。
示例：
输入：
5 1000
输出：
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
与完整背包不同的是，完整背包的物品数量不限，而多个背包只能带指定数量的物品。那么想到的最简单的办法就是把相同的物品分开。比如有N个A项，分成a1 a2 a3 a4…an然后用01背包法求解。然后我们可以编写下面的核心代码：
for(I=1；I=n；i ){
for(j=m；j=0；j - ){
for(k=0；k=s[I]j=k * w[I]；k)
{
dp[j]=max(dp[j]，DP[j-k * w[I]]k * v[I])；//从01背包的状态转移方程中，为第I项增加取K的周期。
}
}
}
从上面的代码可以看出，当s[i]极大时，会消耗大量的时间复杂度，所以一定有优化的方法！然后我们可以优化二进制应该取多少相同的项。我们可以通过以下问题进行研究：
有1000个苹果。你怎么把它们放在10个盒子里？无论我想带多少苹果，我都可以用盒子带。
用二进制的思路是每个方框代表二进制对应的位数，所以210 > 1024应该可以满足题目的条件。那么每个盒子里的苹果是1，2，4，8，16，32，…488(1000-512)。第一箱需要一个苹果，第二件需要两个苹果，一两箱需要三个苹果。那么对于拿1000盒的问题，应该是回收了1000次。优化后只能循环使用10次！然后我们就可以写下面的程序了！
for(I=1；I=n；i ){
for(j=m；j=0；j - ){
for(k=0；k=s[I]j=k * w[I]；k=1)
{
如果((k1)s[i]j=k*w[i])
{
dp[j]=max(dp[j]，DP[j-(s[I]-k)* w[I]](s[I]-k)* v[I])；
}
其他
dp[j]=max(dp[j]，DP[j-k * w[I]]k * v[I])；//从01背包的状态转移方程中，为第I项增加取K的周期。
}
}
}
动态规划解题思路
我们对动态编程的一般想法如下：
判断完动态规划的求解思路后马上定义一个数组，想清楚数组对应的下标和对应的值。
然后根据找题意义的规律，找出初始状态和一些边界条件。
根据列表数据找到状态转移方程。
最后根据状态转移方程编写程序。
以上就是本文对C语言动态规划背包问题的详细解释。关于C语言背包的更多信息，请搜索我们之前的文章或者继续浏览下面的相关文章。希望大家以后能多多支持我们！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。