关于 混合背包（完全背包、多重背包、01背包） 的解题思路（C语言）

注意：观看本篇文章需要一定基础，如果你不会解决背包问题，这里建议先去学习一下。

解题思路：

与多重背包差不多，不过要加入一个判断：当物品数量为0时，使用完全背包；如果不为0，则使用多重背包（当物品数量为1时就是01背包）。

下面是参考代码，我进行了优化，使用一维数组解决。

对了这里提一下，本题的输出样例是错误的，不是1040，应该是11。

参考代码：

#include <stdio.h>
#define max(x,y) (x)>(y)?(x):(y)//模拟c++的max函数，用来判断最大值
  
int main() {
    int m,n;//背包重量和物品数量
    scanf("%d%d",&m,&n);
      
      //这里的动态分配我是图方便才这么写的，考试不建议这么写，容易被扣分，
      //一般来说动态分配需要使用malloc来进行内存申请
    int dp[m+1];
    int weight[n+1],value[n+1],number[n+1];
  
    //初始化
    for(int i=0; i<=n; ++i) {
        weight[i]=0;
        value[i]=0;
        number[i]=0;
    }
    for(int i=0; i<=m; ++i) {
        dp[i]=0;
    }
  
    for(int i=1; i<=n; ++i) {
        scanf("%d%d%d",&weight[i],&value[i],&number[i]);
    }
  
    for(int i=1; i<=n; ++i) {  //遍历每一个物品
        if(number[i]!=0) {  //在这里加入判断，物品数量不为0就进执行多重背包
            for(int k=1; k<=number[i]; ++k) {
            //这里是多重背包的代码
                for(int j=m; j>0; --j) {
                    if(j>=weight[i]) {
                        dp[j]=max(value[i]+dp[j-weight[i]],dp[j]);
                    }
                }
            }
        } else {  //否则执行完全背包
            for(int j=1; j<=m; ++j) {
                if(j>=weight[i]) {
                    dp[j]=max(value[i]+dp[j-weight[i]],dp[j]);
                }
            }
        }
    }
  
    printf("%d\n",dp[m]);
    return 0;
}