Bessie's weight problem [01 backpack]

subject ：

Bessie Like many of her sisters , Because from Farmer John The grass in our country eats too much delicious grass and grows too much fat . therefore FJ Put her on a very strict diet . She can't eat too much every day H(5 ≤ H ≤ 45,000)  Kg of hay .Bessie You can only eat a whole bale of hay ; When she started eating a bunch of hay, she couldn't stop . She has a complete N (1 ≤ N ≤ 500) A list of bales of hay to give her for dinner . Give a list of the weight of each bale of hay Si (1 ≤ Si ≤ H), seek Bessie How much hay can you eat without exceeding the diet limit （ Notice that once she starts eating a bale of hay, she will eat it all up ）.

Input format

first line : Two integers separated by spaces : H and N.

The first 22 To the first N+1 That's ok : The first i+1 Line is a single integer , It means the first one ii The weight of a bale of hay S_iSi​.

Output format

first line : A single integer represents Bessie How many kilograms of hay can you eat within the limit .

Sample Input

56 4
15
19
20
21

Sample Output

56

Answer key ：

#include<iostream>
#include<algorithm>
using namespace std;
int k[510];
int dp[45010];
int main()
{
	int h,n;
	scanf("%d%d",&h,&n);    // Enter the total number of hay 、 Bale count 
	int i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k[i]);    // Enter the weight of each bale of hay 
	}
	for(i=1;i<=n;i++){
		for(j=h;j>=0;j--){    // flashback 
			if(j>=k[i]){
    			dp[j]=max(dp[j-k[i]]+k[i],dp[j]);
			}
		}
	}
	printf("%d",dp[h]);
	return 0;
}