P1725 0/1背包问题

背包DP模板题，这个屑蒟蒻并没有压缩状态

注释在CODE挺详细的了

CODE

#include<bits/stdc++.h>
using namespace std;
int W[1010],V[1010];
int dp[1010][1010];//dp[前x件物品][已用重量]=对应最大价值 
int m,n; 
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; 
	for(int i=1;i<=n;i++){//枚举第i件物品 
		for(int j=1;j<=m;j++){//插入第i件物品后重量 
			if(j>=W[i]){//插入后重量肯定得比该物件要重吧…… 
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
				//dp[i-1][j] 即为 不选该物件,不选且重量达到j的最优价值 
				//dp[i-1][j-W[i]]+V[i] 即为 选择该物件,那么,可以得出,在没有选择该物件时，重量为j-W[i] 
				//故在该状态+V[i](对应物品的价格) 
			}
			else{
				dp[i][j]=dp[i-1][j];//见上 
			}
		}
	} 
	cout<<dp[n][m];//输出最优结果 
}