这道题多了求路径

路径和求欢迎度的思想差不多，就是用前一个路径的状态推后一个路径的状态

只需考虑能放进去且最优情况时，路径才会发生变化。路径变化在上一个基础上变化。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int a[maxn][maxn];
int w[maxn][maxn];
int main()
{
	memset(a,0,sizeof(a));
	int m,n;
	while(cin>>m>>n)
	{
		vector<int>result[maxn];
		for(int i=1;i<=n;i++)
			cin>>w[i][0]>>w[i][1];
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=m;j++)
			{
				if(j>=w[i][0])
				{
					if(a[i-1][j-w[i][0]]+w[i][1]>a[i-1][j])
					{
						result[j]=result[j-w[i][0]];
						result[j].push_back (i);
					}
					a[i][j]=max(a[i-1][j-w[i][0]]+w[i][1],a[i-1][j]);
				}
				else
					a[i][j]=a[i-1][j];
			}				
		}
		cout<<a[n][m]<<endl;
		if(a[n][m]!=0)
		{
			for(int i=0;i<result[m].size();i++)
				cout<<result[m][i]<<" ";
			cout<<endl;
		}
	}
	return 0;
}