1924: 蓝桥杯算法提高VIP-01背包

解题思路:非常经典的dp题目

注意事项:必须把横向第一行和纵向第一行归零

参考代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
        int x[n+5][m+5];//用这种方法必须加加大一点,因为下面用的时候都是从1开始等于n或m结束
	int w[n+5],v[n+5];
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=0;i<n;i++)
	{
		x[i][0]=0;
	}
	for(int i=0;i<m;i++)
	{
		x[0][i]=0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(w[i]>j)
			{
				x[i][j]=x[i-1][j];
			}
			else
			{
				x[i][j]=max(x[i-1][j],x[i-1][j-w[i]]+v[i]);
			}
		}
	}
	cout<<x[n][m]<<endl;
	return 0;
}