0-1背包问题详解-动态规划-两种方法

问题描述：

给定n种物品和一背包。物品i的重量为wi，其价值为vi， 背包容量为c。问应如何选择装入背包中的物品，使得背入背包的物品的总价值最大？

解析：

此问题形式化的描述是，给定c > 0, wi, vi, 1 <= i <= n（c为背包容量）, 要找出一个n元0-1向量（x1, x2, ... , xn）,xi ∈ {0, 1}, 1 <= i <= n, 使得∑ wixi (i 从 1 到 n 求和）<= c ，而且∑ wixi (i 从 1 到 n 求和）达到最大。因此0-1背包问题是一个特殊的整数规划问题。

方法1：

递归关系：(这里与课本的描述不同个人感觉课本的“加”比较难理解, 这里用的“减”， 相信我继续看下去QAQ， 方法2用课本的方法“加”)

设所给0-1背包问题的子问题的最优值为m[i][j], 即m[i][j]的含义是是在背包容量为j，可选物品为1, 2, 3, ..., i 时的0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可建立计算m[i][j]的递归式如下：

m[i][j] = max{m[i - 1][j], m[i - 1][j - w[i]] + v[i]}     j >= w[i];

            = m[i - 1][j]                                                    j < w[i];

递归关系流程化：

1：如果不放入第 i 件物品，则问题转换为“前i - 1件物品放入容量为 j 的背包中”；

2：如果放入第 i 件物品，则问题转化为“前i - 1件物品放入容量为 j - w[i] 的背包中”，此时的最大值为 max{m[i - 1][j], m[i - 1][j - w[i]] + v[i] }.

代码：

/*
输入样例 1:
3 10
4 3
5 4
6 5
输出为:
最优解为 : 11
选择的物品的序号为 :
2 3
输入样例 2:
5 10
6 2
3 2
5 6
4 5
6 4
输出为:
最优解为 : 15
选择的物品的序号为 :
1 2 5
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
int n; //物品个数
int c; //包的容量
int value[MAX]; //物品的价值
int weight[MAX]; //物品的重量
int x[MAX]; //n元0-1向量
int m[MAX][MAX]; //解的容器
void Input()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &value[i], &weight[i]);
}
//创建最优解
void Knapsack()
{
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i) //逐行填表，i表示当前可选物品数，j表示当前背包的容量, 也就是从低到顶。 
    {
        for(int j = 1; j <= c; ++j)
        {
            if(j < weight[i])
                m[i][j] = m[i - 1][j];
            else
            {
                m[i][j] = max(m[i - 1][j], m[i - 1][j - weight[i]] + value[i]);
            }
        }
    }
}
//获取最优解(即设法将求得的最优解输出出来)
void Traceback()
{
    int cc = c;
    for(int i = n; i > 1; --i)
    {
        if(m[i][cc] == m[i - 1][cc])
            x[i] = 0;
        else
        {
           x[i] = 1;
           cc -= weight[i];
        }
    }
    if(cc >= weight[1])
        x[1] = 1;
 
}
void Output()
{
    cout << "最优解为 : " << m[n][c] << endl;
    cout << "选择的物品的序号为 :" << endl;
    for(int i = 1; i <= n; ++i)
        if(x[i] == 1)
         cout << i << " ";
    cout << endl;
}
int main()
{
    Input();
    Knapsack();
    Traceback();
    Output();
}

参考博客 ：https://www.cnblogs.com/vincently/p/4804225.html， 补充了Traceback()求解的过程， 完善了代码。

方法2：（解释见代码注释）

递归关系：

设所给0-1背包问题的子问题的最优值为m[i][j], 即m[i][j]的含义是背包容量为j，可选物品为i, i + 1, ... n 时的0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可建立计算m[i][j]的递归式如下：

m[i][j] = max{m[i + 1][j], m[i + 1][j - w[i]] + v[i]}     j >= w[i];

            = m[i + 1][j]                                                    j < w[i];

递归关系流程化：

1：如果不放入第 i 件物品，则问题转换为“i + 1, i + 2,  ..... , n件物品放入容量为 j 的背包中”；

2：如果放入第 i 件物品，则问题转化为“i + 1, i + 2,  ..... , n 件物品放入容量为 j - w[i] 的背包中”，此时的最大值为 max{m[i + 1][j],  m[i + 1][j - w[i]] + v[i]}.

与方法1的区别：

请先务必先看懂方法1~。

首先我们知道求最优解的过程就是填表m的过程。

 方法1是从第一行开始填表m，而方法2是从第n行开始填表m即（两种方法都是是从底往上求解，不过方法一是可选物品从1-> i(从左到右)，方法二是可选物品从i -> n(从右向左）。这就是区别。而思路完全一样。请务必好好想想，然后就会恍然大悟٩(๑>◡<๑)۶ 

代码：

总的来说方法2比方法1运行速度快。

/*
输入样例 1:
3 10
4 3
5 4
6 5
输出为:
最优解为 : 11
选择的物品的序号为 :
2 3
输入样例 2:
5 10
6 2
3 2
5 6
4 5
6 4
输出为:
最优解为 : 15
选择的物品的序号为 :
1 2 5
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
int n; //物品个数
int c; //包的容量
int value[MAX]; //物品的价值
int weight[MAX]; //物品的重量
int x[MAX]; //n元0-1向量
int m[MAX][MAX]; //解的容器
void Input()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &value[i], &weight[i]);
}
//创建最优解
void Knapsack()
{
    int jMax = min(c, weight[n] - 1);
 
    //这一块填最后m表的最后一行
    /*
      解释一下就是：“在可选的物品只有n即最后一个物品n，包的容量为c时” 的最优解。
      第一个for循环：
      容易知道在背包容量为0 ~ weight[n] - 1的时候背包是放不进去物品n的，如果背包
      的容量小于物品n的质量，背包也是放不进去物品的，所以从weight[n] - 1 和 c 中
      选择一个较小的，然后m[n][0:jMax]的值为零
      第二个for循环：
      自然可知当背包容量大于weigh[n]的时候,由于其可选则的物品只有 物品n，因此m[n][weight[n]:c]
      的值全部为value[n].
    */
    for(int j = 0; j <= jMax; ++j)
        m[n][j] = 0;
    for(int j = weight[n]; j <= c; ++j)
        m[n][j] = value[n];
 
    //这一块是填m表的2 ~ n - 1行，容易理解
    for(int i = n - 1; i > 1; --i)
    {
        jMax = min(c, weight[i] - 1);
        for(int j = 0; j <= jMax; ++j)
            m[i][j] = m[i + 1][j];
        for(int j = weight[i]; j <= c; ++j)
            m[i][j] = max(m[i + 1][j], m[i + 1][j - weight[i]] + value[i]);
    }
 
    //这里是填m表的第一行，好好理解一下，不难，好好考虑一下 φ(>ω<*)
    m[1][c] = m[2][c];
    if(c >= weight[1])
        m[1][c] = max(m[1][c], m[2][c - weight[1]] + value[1]);
}
//获取最优解(即设法将求得的最优解输出出来)
void Traceback()
{
    int cc = c;
    for(int i = 1; i < n; i++)
        if(m[i][cc] == m[i + 1][cc])
           x[i] = 0;
        else
        {
            x[i] = 1;
            cc -= weight[i];
        }
        x[n] = (m[n][cc]) ? 1 : 0;
}
void Output()
{
    cout << "最优解为 : " << m[1][c] << endl;
    cout << "选择的物品的序号为 :" << endl;
    for(int i = 1; i <= n; ++i)
        if(x[i] == 1)
         cout << i << " ";
    cout << endl;
}
int main()
{
    Input();
    Knapsack();
    Traceback();
    Output();
//    cout << "*******" << endl;
//    for(int i = 1; i <= n; ++i)
//    {
//        for(int j = 1; j <= c; ++j)
//            cout << m[i][j] << " ";
//        cout << endl;
//    }
}

方法三：基于以方法一的路径压缩

思路：

定义m[j] : m[j]为背包容量为 j 时（注意不是剩余容量），背包装入的最大value。

解题流程：遍历 i （可选物品为 1 ~ i），m[j] = max{ m[j], m[j - weight[i]] + value[i] }

缺点：无法求出选中了哪些物品

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1024;
int n; //物品个数
int c; //包的容量
int value[MAX]; //物品的价值
int weight[MAX]; //物品的重量
int x[MAX]; //n元0-1向量
int m[MAX]; //解的容器
void Input()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &value[i], &weight[i]);
}
//创建最优解
void Knapsack()
{
    memset(m, 0, sizeof(m));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = c; j >= weight[i]; --j)
        {
            m[j] = max(m[j], m[j - weight[i]] + value[i]);
        }
    }
}
void Output()
{
    cout << "最优解为 : " << m[c] << endl;
    cout << endl;
}
int main()
{
    Input();
    Knapsack();
 
    Output();
}