学步园

背包大小为m，对于每一个物品，枚举背包大小j(m到w)，对于此物品（重量w、价值v），如果dp[j-w]+v大于dp[j]，则采用该方案(dp[j]=dp[j-w]+v)

最后dp[实际背包大小m]就是最大价值

#include <iostream>
using namespace std;
#define SIZE 12881
int dp[SIZE];
int main(int argc, char* argv[])
{
	//freopen("i://input.txt","r",stdin);
	int n,m;
	memset(dp,0,SIZE);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		int w,v;

		scanf("%d%d",&w,&v);
		for(int j=m;j>=w;j--){
			int temp = dp[j-w]+v;
			if(temp>dp[j])
				dp[j] = temp;
		}
		
	}
	printf("%d\n",dp[m]);
	return 0;
}