51nod 01 가방(DP)

727 단어
입력
 1 ,2   ,N W       。N      ,W      。(1 <= N <= 100,1 <= W <= 10000)
 2 - N + 1 ,  2   ,Wi Pi,              。(1 <= Wi, Pi <= 10000)

출력

입력 예
3 6
2 5
3 8
4 9

출력 예
14
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int v[500],w[500],dp[20000];
int main()
{
	int n,m,i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>w[i]>>v[i];
	for(i=1;i<=n;i++) {
		for(j=m;j>=w[i];j--)
		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	}
	cout<<dp[m]<<endl;
	return 0;
}

좋은 웹페이지 즐겨찾기