01背包——二维动态规划【c++】代码实现-创新互联

今天学了01背包，就想来讲一讲，正好回顾一下（BZOJ上的题目）。

十多年的加查网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。网络营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整加查建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联公司从事“加查网站设计”,“加查网站推广”以来，每个客户项目都认真落实执行。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背包这个名字把我唬住了

#includeusing 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;
}

待续更

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：01背包——二维动态规划【c++】代码实现-创新互联
文章链接：http://cqcxhl.cn/article/dsigdg.html