第一道入门dp,看了好多大神的评论才理解了一些思想。
用的是一维数组进行的模拟
#include<iostream>
//#include<fstream>
using namespace std;
int weight[12881]= {0},value[12881]={0},dp[12881]={0};
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
//ifstream cin("in.txt");
int n,m,j;
cin>>n>>m;
for(int i = 0; i < n; i ++)
cin>>weight[i]>>value[i];
for(int i = 0; i < n; i ++)
{
for( j = m; j >= weight[i]; j --)
dp[j] = max(dp[j],(dp[j-weight[i]]+value[i]));//这一步应该仔细想想，实在不理解可以在编译器上调试，看看运行进程
}
cout<<dp[m]<<endl;
}