今天学了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;
}

待续更