01背包简介

01背包是动态规划一个重要的基础。

像它的名字，0和1就代表取或不取。

例子：

描述

经典0—1背包问题,有n个物品，编号为i的物品的重量为w[i]，价值为c[i]，现在要从这些物品中选一些物品装到一个容量为m的背包中，使得背包内物体在总重量不超过m的前提下价值尽量大。

输入描述

第1行:两个整数，n(物品数量，1<=n≤100)和m(背包容量,0<=m≤1000)。

第2..n+1行：每行二个整数w[i]，c[i]，表示每个物品的重量和价值。

输出描述

仅一行，一个数，表示最大总价值。

用例输入 1 

4 6
1 4
2 6
3 12
2 7

用例输出 1 

23

现在就需要考虑每样物品是拿还是不拿。

这就要用到状态转移方程了。

我们可以用：当来到第i件物品，且背包大小为j时，最大价值为dp[i][j]。

现在，想要dp[i][j]的值最大，我们对第i件物品只有两种状态：取（1）或不取（0）。

如果不取，那么dp[i][j]的最大值即为来到第i-1件物品时的最大值，即dp[i][j]=dp[i-1][j]。

如果取，那么需要预留v[i]个空间，同时也获得c[i]个价值，即dp[i][j]=dp[i][j-v[i]]+c[i]。

想要dp[i][j]最大，就是在这两个值之间取max,即dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+c[i])。

这就是状态转移方程。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,m,dp[110][1010],c[110],v[110],mx;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>c[i]>>v[i];            }for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(c[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);else dp[i][j]=dp[i-1][j];}}cout<<dp[n][m];return 0;
}