RQNOJ-PID39 / 飲食問題

題目描述

Bessie 正在減肥，是以她規定每天不能吃超過 C (10 <= C <= 35,000)卡路裡的食物。農民 John 在戲弄她，在她面前放了B (1 <= B <= 21) 捅食物。每桶内都有某個機關卡路裡(範圍：1..35,000)的食物(不一定相同)。Bessie 沒有自控能力，一旦她開始吃一個桶中的食物，她就一定把這桶食物全部吃完。

Bessie 對于組合數學不大在行。請确定一個最優組合，使得可以得到最多的卡路裡，并且總量不超過C。

例如，總量上限是40卡路裡， 6 桶食物分别含有7, 13, 17, 19, 29, 和 31卡路裡的食物。Bessie可以吃7 + 31 = 38卡路裡，但是可以擷取得更多： 7 + 13 + 19 = 39卡路裡。沒有更好的組合了。

輸入格式

共兩行。

第一行，兩個用空格分開的整數： C 和 B

第二行，B個用空格分開的整數，分别表示每桶中食物所含的卡路裡。

輸出格式

共一行，一個整數，表示Bessie能獲得的最大卡路裡，使她不違反減肥的規則。

輸入：

40 6

7 13 17 19 29 31

輸出：

39

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[36000],val[30];
int main()
{
	int m,n,i,j;
	scanf("%d%d",&m,&n);
	for(i=0;i<n;i++)
		scanf("%d",&val[i]);
	memset(f,0,sizeof(f));
	for(i=0;i<n;i++)
	{
		for(j=m;j>=val[i];j--)
		{
			f[j]=max(f[j],f[j-val[i]]+val[i]);
		}
	}
	printf("%d\n",f[m]);
	return 0;
}