【蓝桥杯】背包问题--DP动态规划入门

解题思路:

DP动态规划的思路就是：

在有 K 件物品（每个物品都有自己的重量与价值，记为w[i]、v[i]）、背包容量为 W 时可以获取的最大价值，对于这种情况可以记为 f（K,W），值为可以获取的最大价值

在这种情况下有两种方式可以求解：

第一种就是：不拿第 K 件物品，在 1-（K-1）的范围内挑选物品，此时问题变为：在 K-1 件物品、背包容量为 W 时可以获取的最大价值，记为f（K-1,W）;

第二种就是：拿第 K 件物品，此时背包容量为 W-（第 K 件物品所占的重量），已获取的价值为（第 n 件物品所具有的的价值），此时的问题变为在 n-1 件物品、

背包容量为 W-w[K] 时可以获取的最大价值,记为 f（K-1,W-W[K]）+ V[K]；

原问题的解就是两种情况中价值较大的那一个；

注意事项:

1.可以列出一个矩阵来记录所有状态下的解，val【i】【j】,i 用来枚举出 n 件物品，j 用来枚举背包容量

2.要列出状态转移方程，该题的状态转移方程为：

3.以题中例子为例：

有三个物品，背包容量为5；

参考代码:

//简单背包问题 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200; 
const int maxm = 5000;  //最多可以装5000重量的东西
int val[maxn+10][maxm+10];   //表示当前状态可以装的最大值，【物品个数】【背包容量】 
int w[maxn+10];  //存储物品的重量 
int v[maxn+10];  //存储物品的价值 
int main(){
	memset(val,0,sizeof(val));
	int n,m;
	cin>>n>>m;
	int ww,vv; 
	//存储每个物品的数据    [0][i]与[i][0]都是0，一个代表可以拿0个物品，一个是还有0个剩余重量 
	for(int i=1;i<=n;++i){
		cin>>ww>>vv;
		w[i]=ww;
		v[i]=vv;
	}
	//开始处理
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(w[i]>j)   //j表示可以拿多大重量的物品
				val[i][j] = val[i-1][j];
			else
				val[i][j] = max(val[i-1][j],val[i-1][j-w[i]]+v[i]); 
		}
	} 
	cout<<val[n][m]<<endl;
	return 0;
}