动态规划之背包问题（C语言）

大家好，又见面了，我是你们的朋友全栈君。

动态规划

动态规划（英语：Dynamic programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题
动态规划思想大致上为：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
由于通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

背包问题

背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使得物品的总价格最高。
背包问题是典型的动态规划问题。

而背包问题还存在需要恰好装满背包和不需要恰好装满两种情况
这篇文章所探讨的所有背包问题都是建立在不需要恰好装满的情况下

由简单背包问题的基础上又衍生出许多问题都可以采用动态规划解决。
例如：
1. 01背包问题（每种物品只有一件，放或者不放）
2. 完全背包问题（每件物品有无限件可用）
3. 多重背包问题（每件物品有n[i]件可用）

01背包问题

题目：有N件物品和一个容量为V的背包。第i件物品的费用是weight[i]，价值是value[i]。求将哪些物品装入背包可使价值总和最大。

01背包问题是最基础的背包问题，”01”的意思是：每种物品仅有一件，放为“1”，不放为“0”。
我们假定f[i][v]为将前i件物品前恰好放入一个容量为V的背包中可获得的最大价值
则其状态转移方程是：

f[i][V]=max{f[i-1][V],f[i-1][V-weight[i]]+value[i]}

由上图可知，背包问题可以简化为“将前i件物品放入容量为V的背包中”的问题，而这个问题可以优化为，“不放第i件物品“和“放第i件物品“的问题。

如果不放第i件物品，问题为将前i-1件物品放入容量为V的背包中，总价值为f[i-1][v]

如果放第i件物品，问题为前i-1件物品放入剩下的容量为V-weight[i]的背包中，价值为f[i-1][V-weight[i]]+value[i]
代码部分较为简单，主要学习动态规划这种思想：

    for (int i=1; i<=N; i++)  
        for (int j=1; j<=M; j++)  
        { if (weight[i]<=j) { f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]); }  
            else  
                f[i][j]=f[i-1][j];  
        }  

该算法的时间复杂度一定降到最低，但是我们还可以通过压缩空间复杂度的方式优化代码，方法就是将二维数组f[i][j]转化为一维数组[j]只需将完整程序稍作修改即可，这里只给出核心代码。

    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= weight[i]; --j)
            f[j] = max(f[j], f[j - weight[i]] + value[i]);  

具体代码如下：

#include<stdio.h> 
#define V 1500 
int f[10][V];//全局变量，自动初始化为0 
int weight[10];  
int value[10];  
#define max(x,y) (x)>(y)?(x):(y) 
int main()  
{  

    //状态转移方程 f[i+1][j]=max{f[i][j],f[i][j-weight[i+1]+value[i+1]}
    int N,M; 
    freopen("1.txt","r",stdin); 
    scanf("%d%d",&N,&M);//N物品个数 M背包容量 
    for (int i=1;i<=N; i++)  
    {  
        scanf("%d%d",&weight[i],&value[i]); 
    }  
    //动态规划
    for (int i=1; i<=N; i++)  
        for (int j=1; j<=M; j++)  
        {  
            if (weight[i]<=j)  
            {  
                f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]);  
            }  
            else  
                f[i][j]=f[i-1][j];  
        }  
      printf("%d\n",f[N][M]);//输出最优解
 }

到这里已经基本实现01背包问题，但是该程序在输出的时候，只能输出最后的价值，不能知道选择的物品是哪个。在这里我们定义一个数组x[i]，对于每一个物品，如果被选择置为“1”，否则为“0”。通过这样的方式来实现。
修改之后的代码如下：

#include<stdio.h> 
#define V 100 
int f[10][V];//全局变量，自动初始化为0 
int weight[10];  
int value[10];  
#define max(x,y) (x)>(y)?(x):(y) 
int main()  
{  
    //初始化
    int N,M; 
    freopen("1.txt","r",stdin); 
    scanf("%d%d",&N,&M);//N物品个数 M背包容量 
    for (int i=1;i<=N; i++)  
    {  
        scanf("%d%d",&weight[i],&value[i]); 
    }  
    //动态规划分析
    for (int i=1; i<=N; i++)  
        for (int j=1; j<=M; j++)  
        {  
            if (weight[i]<=j)  
            {  
                f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]);  
            }  
            else  
                f[i][j]=f[i-1][j];  
        }  
      printf("%d\n",f[N][M]);//输出最优解

     //输出选择的物品
    int j = M;
    int x[V];
    for(int i=N; i>0; --i)
    {
        if(f[i][j] > f[i-1][j])
        {
            x[i-1] = 1;
            j = j - weight[i-1];//装入第i-1个宝石后背包能装入的体积就只剩下j - V[i-1]
        }
    }
    for(int i=0; i<N; ++i)  
        printf("%d ", x[i]);  

}   

完全背包问题

题目：有N件物品和一个容量为V的背包。第i件物品的费用是weight[i]，价值是value[i]。每件物品可以无限选用，求将哪些物品装入背包可使价值总和最大。
完全背包问题不设定物品取用上限

对于算法的优化我们可以这样想：
在01背包问题中，我们要保证第i次循环中的f[i][v]是由f[i-1][V-weight[i]]递推而来，每一次都是“加选出一个（即一种）物品”而这种方式同时也保证了每件物品只选一次。
而完全背包问题的特点刚好是每种物品可选无限件，所以在考虑“加选出一个（即一种）物品”时就是单纯的考虑“加选出一个（可能为同一种）物品”，这样我们就需要考虑选入的物品是已经选入的情况。相比来说，反而简化了代码。

同样，我们假定f[i][v]为将前i件物品前恰好放入一个容量为V的背包中可获得的最大价值
则其状态转移方程是：

f[i][V]=max{f[i-1][V],f[i-1][V-k*weight[i]]+k*value[i]}

0<=k*weight[i]<=v，其中0<=k<=V/weight[i+1]

该状态方程等价于f[i][v]=max{f[i-1][v],f[i-1][V-weight[i]]+value[i]}
代码部分如下：

    for(int i = 1; i <= N; ++i)
        for(int j = 0; j <= M; ++j)
            for(int k = 0; k * weight[i] <= j; ++k)
            f[i][j] = max(f[i][j], f[i - 1][j - k * weight[i]] + k * value[i]);

一维数组优化：

    for(int i = 1; i <= N; ++i)
        for(int j = weight[i]; j <= V; ++j)
            f[j] = max(f[j], f[j - weight[i]] + value[i]); 

具体代码如下：

#include<stdio.h> 
#define V 1500 
int f[10][V];//全局变量，自动初始化为0 
int weight[10];  
int value[10];  
#define max(x,y) (x)>(y)?(x):(y) 
int main()  
{  
    //f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}，其中0<=k<=V/weight[i+1]

    //f[j]=max(f[j],f[j-weight[i]]+value[i]) 
    int N,M;  
    //初始化
    freopen("1.txt","r",stdin); 
    scanf("%d%d",&N,&M);//N物品个数 M背包容量 
    for (int i=1;i<=N; i++)  
    {  
        scanf("%d%d",&weight[i],&value[i]); 
    }  
     //动态规划
    for(int i = 1; i <= N; ++i)
        for(int j = 0; j <= M; ++j)
            for(int k = 0; k * weight[i] <= j; ++k)
            f[i][j] = max(f[i][j], f[i - 1][j - k * weight[i]] + k * value[i]);
     printf("%d",f[N][M]);//输出最优解 

}

多重背包问题

题目：有N件物品和一个容量为V的背包。第i件物品最多有n[i]个，每个的费用是weight[i]，价值是value[i]。每件物品最多可以选用相应的最大个数，求将哪些物品装入背包可使价值总和最大。
多重背包问题设定物品选择上限
代码部分如下：

    for(int i = 1; i <= N; ++i)
        for(int j = 0; j <= V; ++j)
            for(int k = 0; k <= num[i] && k * weight[i] <= j; ++k)
                f[i][j] = max(f[i-1][j], f[i - 1][j - k * weight[i]] + k * value[i]);

一维数组优化：

    for(int i = 1; i <= N; ++i)
        for(int j = V; j >= 0; --j)
            for(int k = 1; k <= num[i] && k * weight[i] <= j; ++k)
                f[j] = max(f[j], f[j - k * weight[i]] + k * value[i]);  

具体代码如下：

#include<stdio.h> 
#define V 1500 
int f[10][V];//全局变量，自动初始化为0 
int weight[10];  
int value[10];   
int num[10];
#define max(x,y) (x)>(y)?(x):(y) 
int main()  
{  
    //f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}，其中0<=k<=V/weight[i+1]

    //f[j]=max(f[j],f[j-weight[i]]+value[i]) 
    int N,M,cur;  
    freopen("2.txt","r",stdin); 
    scanf("%d%d",&N,&M);//N物品个数 M背包容量 
    for (int i=1;i<=N; i++)  
    {  
        scanf("%d%d%d",&weight[i],&value[i],&num[i]); 
    }  

    for(int i = 1; i <= N; ++i)
        for(int j = 0; j <= V; ++j)
            for(int k = 0; k <= num[i] && k * weight[i] <= j; ++k)
                f[i][j] = max(f[i-1][j], f[i - 1][j - k * weight[i]] + k * value[i]);
      printf("%d\n",f[N][M]);//输出最优解
}

注：由于测试输入数据较多，程序可以采用文件输入
5 10
2 6
2 3
6 5
5 4
4 6
多重背包需要输入每件物品的可选用次数，所以它的输入文件有所不同
5 10
2 6 1
2 3 1
6 5 1
5 4 1
4 6 1
之所以将次数都定为1，是说明01背包问题是多重背包的一种特殊情况。