2021-10-12

#define _CRT_SECURE_NO_WARNINGS
#include
#include
int main()
{
int N, W;
scanf("%d %d", &N, &W);
int value[102], weight[102];
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &value[i], &weight[i]); //输入
}
int dp[102][2002];
int count[102][2002]; //计数
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <=W; j++)
{
count[i][j] = 0;
}
}
for (int i = 0; i <= W; i++)
{
dp[0][i] = 0;
}
for (int i = 0; i <= N; i++)
{
dp[i][0] = 0;
}
//以上都是初始化

for (int i = 1; i <= N; i++)
{
	for (int j = 1; j <= W; j++)
	{
		if (j >= weight[i])
		{
			//dp[i][j] = fmax( dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i] );
			if (dp[i - 1][j] > dp[i - 1][j - weight[i]] + value[i])
			{
				dp[i][j] = dp[i - 1][j];
				count[i][j] = count[i - 1][j];
			}
			else
			{
				dp[i][j] = dp[i - 1][j - weight[i]] + value[i];
				count[i][j]= count[i - 1][j - weight[i]]+1;
			}
			if (dp[i][j] < 0)        //错误抛出
			{
				printf("%dn", dp[i][j]);
				printf("%d %dn",i,j);
			}			
		}				
		else
		{
			dp[i][j] = dp[i - 1][j];
			count[i][j] = count[i - 1][j];
			//printf("%dn", dp[i][j]);
		}				
	}
}
printf("%d %d", dp[N][W],count[N][W]);

}