博客

问题描述

有一个背包，容量为M。有N种物品，每种物品有其重量Wi与价值Vi。将这些物品的一部分放入背包，每种物品可以放任意多个，要求总重量不超过容量，且总价值最大。

输入格式

第一行为N, M。

之后N行，每行为Wi, Vi。

输出格式

一个数，为最大价值。

样例输入

3 20

15 16

6 6

7 5

样例输出

18

数据规模和约定

N, M<=1000。

代码

#include<stdio.h>
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int w[n+1],v[n+1]; 
	int i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
	}
	int dp[m+1];
	for (i = 0; i <= m; i++) 
		dp[i] = 0;
    for (i = 1; i <= n; i++)
    {
         for (j = 1; j<=m; j++)
         {
         	if(j>=w[i]&&dp[j]<(dp[j - w[i]]+v[i]))
            	dp[j]=dp[j - w[i]]+v[i];
         }
	}
    printf("%d", dp[m]);
	return 0;
}