DP背包问题——01背包

引言

        动态规划是C++中一个很常用的算法。我们会发现大部分算法题都可以使用动态规划解决。在动态规划中最为基础的可以说就是背包问题。从本章开始我将给大家介绍各种类型的背包问题，大家一定要抓住背包之间的不同点，灵活的在算法题目中运用。那么本文我们先来介绍一下01背包。

01背包

        01背包问题是一个经典的动态规划问题，在给定背包容量和一组物品的重量和价值的情况下，目标是选择一些物品放入背包中，使得它们的总重量不超过背包容量，同时获得的总价值最大。

        我们可以来看下面这道01背包的模板题。

【题目描述】

有一个容量为m的背包,有n件物品可以挑选,每个物品有2个属性,体积及价值.

求背包能装下的最大价值是多少

【输入格式】

第1行2个正整数,n,m代表物品个数与背包容量.

接下来n行每行2个正整数,wi表示第i个物品的体积,vi表示第i个物品的价值.

【输出格式】

输出1个整数,即能装下的最大价值.

【输入输出样例#1】

输入#1
4 6
1 4
2 6
3 12
2 7

输出#1        23

【数据范围】

1≤n,m≤1000;        1≤Wi, Vi ≤ 400

题目分析

        目前我们有n个物品，要放入一个容量为m的背包，知道每个物品的两个属性-体积和价值。我们知道每个物品只有两种状态---选和不选，这也正是01背包名字的由来。既然每个物品只有两种状态，我们就可以用一个从1到n的循环枚举每一个物品，再分别考虑每件物品是否选择。那么选择物品与什么有关呢?很显然和背包的容量m有关，因此我们可以再写一个循环枚举背包的容量，这里的范围应该是1~m。那么这样我们就写出了一个基础的框架，接下来就要考虑状态转移方程了。

        对于状态转移方程，我们会发现当容量j<w[i]时是不可以选的，因为背包装不下，如果背包能装下，可以选也可以不选。我们分别考虑选和不选的情况。首先是不选择第i个物品，那么我们就可以继承前i-1个物品在容量为j时的价值。如果是选择的情况，就应该是继承前i-1个物品，容量为j-w[i]的价值。为什么是j-w[i]呢？这是因为当我们把第i个物品放入背包后，背包的容量会减少，减少的正是第i个物品的体积也就是w[i]。分析完选和不选的情况后，我们只需要在背包装不下时，考虑不选的情况，在背包能装下时，考虑选和不选的最大值即可，也就是将选和不选两种情况获得的价值max。

        01背包，在使用时一定要注意的就是题目中没有给出每个物品的数量。当每个物品只有一个，有可选可不选时，我们用到的就是01背包。下面附上01背包模板的代码。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int w[N],v[N],f[N][N];
int main() {
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>w[i]>>v[i];
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
f[i][j]=f[i-1][j];
if (j>=w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);
}
}
cout<<f[n][m]<<endl;
    return 0;
}

原文地址：https://blog.csdn.net/haoran2022/article/details/145288298

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！