2131-01背包-动态规划

#include<stdio.h>
int a[31][201];
int max(int a,int b)
{
	return a>b?a:b;
}
void beibao(int M,int N)
{
	int b[N][2];
	for(int i=0;i<N;i++)
	{
		scanf("%d%d",&b[i][0],&b[i][1]);
	}
	for(int k=1;k<=N;k++)
	{
		for(int j=1;j<=M;j++)
		{
			if(b[k-1][0]>j)
			{
				a[k][j]=a[k-1][j];
			}else{
				a[k][j]=max(a[k-1][j],a[k-1][j-b[k-1][0]]+b[k-1][1]);
			}
		}
	}
	/*for(int k=1;k<=N;k++)
	{
		for(int j=1;j<=M;j++)
		{
			printf("%d ",a[k][j]);
		}
		printf("\n");
	}*/
	printf("%d",a[N][M]);
}
int main()
{
	int M,N;
	scanf("%d%d",&M,&N);
	beibao(M,N);
	return 0;
}

解题思路:

注意事项:

参考代码: