nyoj 860 (01 가방 변형)

클릭 하여 링크 열기http://acm.nyist.net/JudgeOnline/problem.php?pid=860

#include 
#include 
#include 
#define Inf 1001000000 
using namespace std;  
const int M=110;		 //       ，    ，              
long dp[M][M*M]; //      dp  dp[i][j]   i      j      
int main()			  //       W        
{								//     dp[n][j]    j && dp[n][j]<=W  
	long W,w[M];
	long i,j,k,n,v[M],sum;
	while(~scanf("%d%ld",&n,&W))
	{
	
		sum=0;
		for(i=1;i<=n;i++)
		{
			scanf("%ld%d",&w[i],&v[i]);
			sum+=v[i]; //      
		} 
		for(i=0;i<=n;i++) //     
		{
			for(j=0;j<=sum;j++)
			{
				dp[i][j]=Inf;
			
			}
		}
		for(i=0;i<=n;i++)
		{
			dp[i][0]=0; //           0 
		}
		
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=M*n;j++)
			{
				if(j>=v[i])
				dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
				else
				dp[i][j]=dp[i-1][j];
			}
		}
		
		for(j=sum;j>=0;j--)
		{
			if(dp[n][j]<=W)
			{
				break;
			}
			
		}
		printf("%ld
",j);
	}
	return 0;
}