View Code of Problem 4041

#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int weight[301], value[301];
int dp[301][301];
int main() {
	int n, bagweight;
	memset(dp, 0, sizeof(dp));
	while (cin >> n >> bagweight)
	{
		for (int i = 0;i < n;i++)
		{
			cin >> weight[i] >> value[i];
		}
		for (int j = 0;j <= bagweight;j++)
		{
			if (j >= weight[0])
				dp[0][j] = value[0];
		}
		for (int i = 1;i < n;i++)
		{
			for (int j = 0;j <= bagweight;j++)
			{
				if (j < weight[i])
					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[n - 1][bagweight] << endl;
	}
	
}