01背包详解

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。 

第三行包含 M 个正整数，代表每种研究材料的价值。

输出

输出一个整数，代表小明能够携带的研究材料的最大价值。

样例输入 复制

6 1
2 2 3 1 5 2
2 3 1 5 4 3

样例输出 复制

5

提示

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。 

数据范围：
1 <= N <= 1000
1 <= M <= 1000
研究材料占用空间和价值都小于等于 1000

#include<iostream>
#include<vector>
using namespace std;
int bagweight,n;
void chose(){
	vector<int>weight(n); //weight
	vector<int>value(n); //value
	vector<vector<int>>dp(n,vector<int>(bagweight+1)); //dp
	for(int i = 0;i < n;i++){
		cin >> weight[i];
	}
	for(int i = 0;i < n;i++){
		cin >> value[i];
	}
	//dp[i][j]:在0-I 个物品任选 放入j 空间的背包中
	//递推关系：每一个物品都有放和不放两个状态；
	//1、不放物品i，那dp[i][j] = dp[i-1][j],继承上一个背包的价值
	//2、放物品i：等于上一个背包的价值，减掉i的重量后(假设能放下),再加上对应的价值，和不放i的价值取最大，因为保证整体最大值
	//dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
	
	//由递推关系可看出，dp[i][j]由左上方和上方推出 
	//初始化：出现dp[i-1]，所以肯定得对dp[0][j]经行赋值，如果容量够，就赋值为对应value值
	//背包容量：j=0时，放不了任何东西，所以,dp[i][0] = 0；
	for(int i = 0;i < n;i++){ //对j=0经行初始化 
		dp[i][0] = 0;
	} 
	
	for(int j = 0;j <= bagweight;j++){ // 对第一个背包进行初始化。 
		if(j >= weight[0]){
			dp[0][j] = value[0];
		}
	}
	
	for(int i = 1;i < n;i++){
		for(int j = 0;j <= bagweight;j++){
			if(j - weight[i] < 0) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
		}
	}
	cout << dp[weight.size()-1][bagweight] << endl;
}
int main(){
	cin >> n >> bagweight;
	chose();
	return 0;
}