动态规划背包详解——01背包

本文主要是介绍动态规划背包详解——01背包，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

       动态规划，Dynamic Programming，简称DP。动态规划是编程算法十分重要的一章，它的种类繁多，分支也十分复杂，并且没有一个固定的模板。DP是运筹学的一个分支，是求解决策过程中最优化的过程。所有DP代码都是有三个步骤：建表、填表、查表。其中，建表就是定义数组并初始化，查表就是在完善后的表中查找需要的答案，而最关键的便是中间的填表。填表的过程是十分复杂的，其中最最重要的一部分便是状态转移方程。状态转移方程是整个代码的核心，状态转移方程错了，整个代码的结果就会谬以千里。

       背包问题是动态规划中一个十分经典的问题，今天，我们先来看看背包问题中最基础的一种——01背包。01背包的意思是，有一个体积为m的背包和n件物品，每件物品都有自己的体积v和价值c，我们的任务就是，选出若干件物品，使得总体积在不超过背包体积的情况下总价值最大。01背包的建表和查表我们就不多说了，我们着重说一下填表的过程。

        （1）第一步，我们的数组定义为f，f[i][j]表示前i个物品，在背包体积为j的情况下可以达到的最大价值。那我们如何推导状态转移方程呢？首先当前的状态需要依赖于之前的状态，可以理解为从初始状态f[0][0]=0开始决策。有n件物品，则需要n次决策，状态f[i][j]就会不断由之前的状态更新而来。

        （2）第二步，当前背包容量如果不够（j<v[i]），没得选，因此前i个物品最优解即为前i-1个物品最优解

                 代码：f[i][j] = f[i-1][j]

        （3）当前背包容量够，可以选，因此需要决策选与不选第i个物品。

                 代码：

                        选第i个物品：f[i][j] = f[i-1][j-v[i]]+w[i]；

                        不选第i个物品：f[i][j] = f[i-1][j]；

                        我们的决策是如何取到最大价值，因此以上两种情况取max()

         01背包完整代码如下：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;
    return 0;
}

　　（代码来自：https://www.acwing.com/solution/content/1374/）

这篇关于动态规划背包详解——01背包的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！