HDU 4508【DP入門の完全リュック】

01リュックサックや完全リュックサックは物が唯一かどうかを見ればいいと判断します.
依然として状態遷移方程式が使用されている.
しかし、01リュックサックは大きいから小さいまで、完全にリュックサックは小さいから大きいです.
中国語の問題は説明しないで、すべて問題の変数によってあげました;
カロリーが満たされた場合に判断すればよい.

#include <bits/stdc++.h>
const int maxn = 100010;
using namespace std ;
int n ,a[maxn],b[maxn],dp[maxn],m; 
int main()
{
	while(cin>>n)
	{
		memset(dp,0,sizeof(dp));
		for(int i = 0 ; i < n ; i++)
		{
			cin>>a[i]>>b[i];
		}
		cin>>m;
		for(int i = 0 ; i<n;i++)
		{
			for(int j=b[i];j<=m;j++)
			{
				dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
			}
		}
		cout<<dp[m]<<endl;
	}
	return 0 ;
}