P2639 [USACO09OCT]Bessie的体重问题

Link

Solution

01背包

Code

#include<iostream>
#include<algorithm>
const int maxn = 45000 * 500 + 10;
using namespace std;
int n, h;
int cao[maxn], f[maxn];

int main() {
    cin >> h >> n;
    for (int i = 1; i <= n; i++)cin >> cao[i];
    for (int i = 1; i <= n; i++)
        for (int j = h; j >= cao[i]; j--)
            f[j] = max(f[j], f[j - cao[i]] + cao[i]);
    cout << f[h] << endl;
    return 0;
}