蓝桥杯 算法提高 01背包

题目：

　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

输入格式

　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。 　　以后N行每行两个数Wi和Vi,表示物品的重量和价值

输出格式

　　输出1行，包含一个整数，表示最大价值。

样例输入

3 5 2 3 3 5 4 7

样例输出

8

数据规模和约定

　　1<=N<=200,M<=5000.

思路：

这道题就是最经典，最简单的01背包问题了，直接用01背包就可以得到结果。

关于01背包，就是有N件物品，一个背包能够放入的重量是M，让你求出来背包中物品的最大价值；

对于背包，我们可以找到一个递推公式：

（1）当背包中剩余可放入物品的重量比这件物品的重量小，那么这件物品不能放入背包中；

（2）当背包中剩余可放入物品的重量比这件物品的重量大，那么这件物品可以放入背包中，也可以不放进背包中；

用一个二维数组来记录这个判断的过程：dp[ ][ ] ;   

其中，dp[X ][Y ]=Z:代表，现在在前X件物品中进行选择，背包剩余的重量是Y，其中，现在这种情况下背包中最大的价值是Z；

那么上面的递推公式就可以表示为：

 

dp[i][j]=dp[i-1][j]；

//背包放不进去了，那么这件物品不能选，所以在前i件物品中选择的最大的价值和前面i-1件物品中进行选择的最大的价值相同；

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

//背包可以放进去这件物品，那么在前i见物品中进行的选择的物品可能会被替换，换或者不换有两种结果，要从这两种结果中选出来最优的结果；上面的式子即使选和不选两种结果的抉择；

代码如下：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,m; int w[5010],v[5010]; int dp[5010][5010]; int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; i++) { scanf("%d%d",&w[i],&v[i]); } for(int i=1; i<=n; i++)//数量； { for(int j=0; j<=m; j++)//背包能放的重量； { if(j<w[i])//放不下； dp[i][j]=dp[i-1][j]; else//可以放下，就有放和不放两种选择； dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); } } printf("%d\n",dp[n][m]); } return 0; }