01背包——二维动态规划c++代码实现
今天学了01背包,就想来讲一讲,正好回顾一下(BZOJ上的题目)。
01背包
所谓01背包,也就是背包的一种,01背包和完全背包的区别就在于,01背包一件物品只能选择一次,而完全背包可以重复选择某件物品,达到价值最大化的问题,总之,背包问题是一种最值问题,要求我们找到最优解,其实用到的动归也有点贪心的思想在里面,每次只考虑当前和以前,不用考虑未来。
01背包的动态规划思路
关于用动归解决的这件事呢,首先给出一个例子吧:
举例
有一个小偷,半夜来到一户人家偷东西,他带了一个背包,这个背包只容的下4磅的物品,有一下一些物品,每个物品只有一个而且不能拆分(顺便说一句,这是01背包的前提),求出带走物品的最大价值。
图解这个例子:
首先,我们要通过列表的方式来实现动态规划,我们先来看看表格:
很显然,行是背包的容量,必须从1-n,才能实现动态规划,前面的是在为后面的做铺垫。
列是各种物品。
在填表的时候,可能会遇到一下情况:
1.物品的数量比背包容量大:
将此格填上0;
2.dp[i - 1][j]格的重量加上这个物品的重量小于等于所限制数量:
此格= dp[i - 1][j] 此物品的数量
3.dp[i - 1][j]格的重量加上这个物品的重量大于于所限制数量:
此格= dp[i - 1][限制重量 - 当前重量] 当前价值
根据这三个情况,我们很容易得出状态转移方程,我们设限制重量为v1,当前重量为v2,当前价值为p2
那么:dp [ i ] [ j ] = max( dp [ i - 1 ] [ j ] p2 , dp [ i - 1] [ v1 - v2 ] p2)
另外若出现第一种情况,则当前格为0;
按照当前的规则,我们可以根据刚才的例子得出下列表格:
01背包代码实现
我们直接通过上述的递推式加上两个循环即可了,代码真的一点也不复杂,刚学的时候01背包这个名字把我唬住了
#include <iostream>
using namespace std;
const int N=1005; //根据题目的要求改变
int v[N],w[N],f[N][N];
int n,m;
int main(){
scanf("%d%d",&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 ){
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]=max(f[i][j],f[i-1][j-v[i]] w[i]);
}
cout << f[m][n];
return 0;
}
待续更
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbhjk
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01