Java教程

动态规划背包详解——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背包的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!