C语言动态规划之背包问题详解

01背包问题

给定n种物品，和⼀个容量为C的背包，物品i的重量是w[i],其价值为v[i]。问如何选择装⼊背包的物品，使得装⼊背包中的总价值最⼤？（⾯对每个武平，只能有选择拿取或者不拿两种选择，不能选择装⼊某物品的⼀部分，也不能装⼊物品多次）

声明⼀个数组f[n][c]的⼆维数组，f[i][j]表⽰在⾯对第i件物品，且背包容量为j时所能获得的最⼤价值。根据题⽬要求进⾏打表查找相关的边界和规律根据打表列写相关的状态转移⽅程⽤程序实现状态转移⽅题演练：

⼀个旅⾏者有⼀个最多能装M公⽄的背包，现在有n件物品，它们的重量分别是W1、W2、W3、W4、…、Wn。它们的价值分别是C1、C3、C2、…、Cn,求旅⾏者能获得最⼤价值。输⼊描述：

第⼀⾏：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30); 第2…N+1⾏：每⾏两个整数Wi，Ci，表⽰每个物品的质量与价值。输出描述：

仅⼀⾏，⼀个数，表⽰最⼤总价值样例：

输⼊：10 42 13 34 57 9输出：12解题步骤

定义⼀个数组dp[i][j]表⽰容量为j时，拿第i个物品时所能获取的最⼤价值。按照题⽬要求进⾏打表，列出对应的dp表。W[i]（质量）V[i]（价值）0123456710

00000000000

2347

1359

001111111110013344444400135560013556991012

对于⼀个动态规划问题设置下标时最好从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];

#include

int max(const int a,const int b){

return a>b ? a:b;}

int main(){

int w[35]={0},v[35]={0},dp[35][210]={0}; int n,m;

scanf(\"%d %d\ int i,j;

for(i=1;i<=n;i++){

scanf(\"%d %d\ }

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]);//判断是否应该拿下 }

else//⼤于背包的当前容量 {

dp[i][j]=dp[i-1][j]; } } }

for(int k=0;k<=n;k++) {

for(int l=0;l<=m;l++) {

printf(\"%d \ }

printf(\"\\n\"); }

printf(\"%d\\n\}

通过运⾏以上程序可以看到最终的输出dp表和我们的预期是相符合的！但是并没有结束，动态规划有⼀个后⽆效性原则(当前状态只与前⼀个状态有关)。那么我们就可以对dp数组进⾏压缩处理，将⼆维数组转换成⼀维数组。每⼀次选择物品对这个数组进⾏更新就可以啦！那么就可以将状态转移⽅程压缩成为 dp[j]=max(dp[j],dp[j-w[i]]+v[i]) 。不过我们需要注意的是在压缩过后我们需要逆序刷新数组的值，如果正序刷新的话就不能保存上⼀个阶段对应获取最⼤价值的值了。那么我们就可以写出以下程序：

#include

int max(const int a,const int b){

return a>b ? a:b;}

int main(){

int w[35]={0},v[35]={0},dp[210]={0}; int n,m;

scanf(\"%d %d\ int i,j;

for(i=1;i<=n;i++){

scanf(\"%d %d\ }

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 \ }

printf(\"\\n\"); }

printf(\"%d\\n\}

可以看出和上⾯输出的dp表并没有什么区别！

完全背包问题

题⽬描述：

设有n种物品，每种物品有⼀个重量及⼀个价值，但每种物品的数量都是⽆限的，有⼀个背包，最⼤载重量为m，今从n中物品中选取若⼲件（同⼀种物品可以多次选取）使其质量⼩于等于m，⽽价值的和为最⼤。输⼊：

第⼀⾏：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30); 第2…N+1⾏：每⾏两个整数Wi，Ci，表⽰每个物品的质量与价值。输出：

仅⼀⾏，⼀个数，表⽰最⼤总价值。样例：

输⼊:10 42 13 34 57 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背包来对完全背包进⾏打表！w[i]（质量）v[i]（价值）0123456710

00000000000

2347

1359

00112233445001334667990013556810101100135569101012

根据表中红⾊标记的数值来看，需要注意的是如果背包的容量不能装下当前物品的质量。那么当前容量所能装下价值最⼤的物品就等于上⼀个物品所能保存的最⼤价值。重点看⼀下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背包使⽤的是上⼀条的数据，所以需要逆序避免覆盖之前的值，⽽完全背包是从当前更新后的数据进⾏相关的操作的 。通过以上分析我们可以写出如下程序：

#include

int max(const int a,const int b){

return a>b ? a:b;}

int main(){

int w[35]={0},v[35]={0},dp[210]={0}; int n,m;

scanf(\"%d %d\ int i,j;

for(i=1;i<=n;i++){

scanf(\"%d %d\ }

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 \ }

printf(\"\\n\"); }

printf(\"%d\\n\}

通过以上代码的输出可以看出打印的dp表和我们推测的并没有什么区别，程序正确！

多重背包问题

题⽬描述：

为了庆祝班级在校运会上取得了全校第⼀名的好成绩，班主任决定开⼀场庆功会，为此拨款购买奖品犒劳运动员。期望拨款⾦额能够购买最⼤价值的奖品，可以补充他们的精⼒和体⼒。输⼊：

第⼀⾏输⼊两个数n（n<=500),m(m<=6000)，其中n代表希望购买的奖品的种数，m表⽰拨款⾦额。

接下来的n⾏，每⾏3个数,w,v,s分别表⽰第i种奖品的价格、价值（价格与价值是不同的概念）和能购买的最⼤数量（买0件到s件均可），其中w<=100,v<=1000,s<=10;输出：

⼀⾏：⼀个数，表⽰此次购买能获得的最⼤价值（注意！不是价格）。⽰例：

输⼊：5 1000输出：80 20 440 50 930 50 740 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) {

if((k<<1)>s[i]&&j>=k*w[i]) {

dp[j]=max(dp[j],dp[j-(s[i]-k)*w[i]]+(s[i]-k)*v[i]); }

else

dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);//从01背包的状态转移⽅程，去增加第i个物品拿k个的循环 } }}

动态规划解题思路

对于动态规划问题我们⼀般的思路如下：

判断是动态规划的解题思路以后⽴马定义⼀个数组，把数组对应的下标、对应的值想清楚。然后根据题⽬意思找规律进⾏打表，找出初始状态以及⼀些边界条件。根据打表的数据找出状态转移⽅程。最后根据状态转移⽅程进⾏编写程序。

到此这篇关于C语⾔动态规划之背包问题详解的⽂章就介绍到这了,更多相关C语⾔ 背包内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！