View Code of Problem 4056

#include<iostream>
using namespace std;
int weight[110],value[110],dp[110][1100];
int main(){
	int w,k;
	cin>>w>>k;
	for(int i=1;i<=k;i++){
		cin>>weight[i]>>value[i];
	}
	for(int i=1;i<=k;i++)
		dp[i][0]=0;
	for(int j=1;j<=w;j++)
		dp[0][j]=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=w;j++)
		{
			if(weight[i]>j){
				dp[i][j]=dp[i-1][j];
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
			}
		}
	}
	cout<<dp[k][w];
}