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

       作为一名大三老学长，我的嵌入式春招找实习之旅好像接近尾声了。春招投递了BAT、美团、华为、oppo、大疆等公司的实习。大多数公司都给了面试机会，尤其是阿里，笔试一道编程题都没有写出来居然还给了面试机会！还是非常感谢这些互联网公司能够给我面试机会的，oppo 的HR面后半个多月了也没有消息，华为投递一个月也没有什么进展。目前已经拿到了大疆、CVTE实习，打算5月去深圳大疆实习！
        尽管已经拿到了实习的机会，但是通过春招发现了很多的知识空白需要填补，毕竟生于忧患，死于安乐嘛。笔试了很多家公司，编程题总结起来就是字符串、动态规划、二叉树、图、BFS、DFS。一个搞嵌入式的为什么要整这么难的笔试题？八成是因为内卷吧！所以为了秋招，把该补的知识还是得赶快补上，该刷的题还是得刷起来！

往期推荐：

       看完这些面试必问的Linux小知识，我保证你面试后会来给我的文章一键三连
       经过笔试和多轮技术面试我居然败给了HR面？

01背包问题

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

• 声明一个数组f[n][c]的二维数组，f[i][j]表示在面对第i件物品，且背包容量为j时所能获得的最大价值。
• 根据题目要求进行打表查找相关的边界和规律
• 根据打表列写相关的状态转移方程
• 用程序实现状态转移方程

真题演练：

       一个旅行者有一个最多能装M公斤的背包，现在有n件物品，它们的重量分别是W₁、W₂、W₃、W₄、…、W_n。它们的价值分别是C₁、C₃、C₂、…、C_n,求旅行者能获得最大价值。

输入描述：

       第一行：两个整数，M（背包容量，M<= 200)和N（物品数量，N<=30);
       第2…N+1行：每行两个整数W_i，C_i，表示每个物品的质量与价值。

输出描述：

       仅一行，一个数，表示最大总价值

样例：

输入：
    10 4
    2 1
    3 3
    4 5
    7 9
输出：
    12

解题步骤

1. 定义一个数组dp[i][j]表示容量为j时，拿第i个物品时所能获取的最大价值。
2. 按照题目要求进行打表，列出对应的dp表。

       对于一个动态规划问题设置下标时最好从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 <stdio.h>
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",&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]);//判断是否应该拿下
            }
            else//大于背包的当前容量
            {
                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]) 。不过我们需要注意的是在压缩过后我们需要逆序刷新数组的值，如果正序刷新的话就不能保存上一个阶段对应获取最大价值的值了。那么我们就可以写出以下程序：

#include <stdio.h>
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",&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行：每行两个整数W_i，C_i，表示每个物品的质量与价值。

输出：

       仅一行，一个数，表示最大总价值。

样例：

输入:
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背包来对完全背包进行打表！

       根据表中红色标记的数值来看，需要注意的是如果背包的容量不能装下当前物品的质量。那么当前容量所能装下价值最大的物品就等于上一个物品所能保存的最大价值。重点看一下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 <stdio.h>
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",&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分别表示第i种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可），其中w<=100,v<=1000,s<=10;

输出：

       一行：一个数，表示此次购买能获得的最大价值（注意！不是价格）。

示例：

输入：
5 1000
输出：
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

       与完全背包不同的是：完全背包每个物品的个数是无限的，而多重背包是每个物品只能拿指定的件数。那么最容易想到的方法就是把相同的物品分开，比如说有n个a物品，就将它分成a₁ a₂ a₃ a₄…a_n然后用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个箱子怎么放，不管我想拿多少个苹果，都可以成箱成箱的拿？

       用二进制的思想就是每一个箱子代表二进制对应的位数，那么2¹⁰大于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个的循环
        }
    }
}

动态规划解题思路

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

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

       不积小流无以成江河，不积跬步无以至千里。而我想要成为万里羊，就必须坚持学习来获取更多知识，用知识来改变命运，用博客见证成长，用行动证明我在努力。
       如果我的博客对你有帮助、如果你喜欢我的博客内容，记得“点赞” “评论” “收藏”一键三连哦！听说点赞的人运气不会太差，每一天都会元气满满呦！如果实在要白嫖的话，那祝你开心每一天，欢迎常来我博客看看。