信息学奥赛一本通 1268：【例9.12】完全背包问题

#include<bits/stdc++.h>
using namespace std;
int m,n;
struct node
{
	int heavy,score;
}item[10000];
int max_sc=-1;
void dfs(int sum,int h,int step)
{
	if (h>m)return;
	if (step==n or h==m)
	{
		if (sum>max_sc)max_sc=sum;
		return;
	}
	for (int i=0;i<=floor((m-h)/(item[step].heavy));i++)
	{
		dfs(sum+(item[step].score)*i,h+(item[step].heavy)*i,step+1);
	}
		
}
int main()
{
	cin>>m>>n;
	for (int i=0;i<n;i++)
	{
		cin>>item[i].heavy>>item[i].score;
	}
	dfs(0,0,0);
	ciut<<max_sc;
	return 0;
}