O(VN)_一维数组01背包

01背包:为什么将二维改成一维要逆序呢：

显然，根据二维的动态方程dp[i] [j] = max(dp[i] [j], dp[i] [ j - v[i] ] + w[i])

dp[i] [j]只取决与i-1行的第 j 个格子与第  j - v[i] 个格子，当改成一维时还是正序的话，

就会将 j 前面的格子给覆盖掉，那么这个时候去找第 j - v[i] 个格子时，他的值就是第 i 行的值，

而不是我想要的i - 1行的值，但是逆序的话从右边往左边覆盖，而我要找的 j - v[i] 的格子永远都只在

j的左边，所以就能保证找的值是正确的

参考代码:

#include<iostream>
using namespace std;
const int M = 10000;
int m, n;
int dp[M], w[M], c[M];
int main(){
	cin>>n>>m;
	for(int i = 0; i < n; i++){
		cin>>w[i]>>c[i];
	}
	for(int i = 0; i < n; i++){
		for(int j = m; j >= 0; j--){
			if(j >= w[i]){
				dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
			}
		}
	}
	cout<<dp[m];
	return 0;
}