题目链接：https://ac.nowcoder.com/acm/contest/984/E/
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Bessie is on a diet where she can eat no more than C (10 ≤ C ≤ 35,000) calories per day. Farmer John is teasing her by putting out B (1 ≤ B ≤ 21) buckets of feed, each with some (potentially non-unique) number of calories (range: 1..35,000). Bessie has no self-control: once she starts on a feed bucket, she consumes all of it.
Bessie is not so good at combinatorics. Determine the optimal combination of feed buckets that gives Bessie as many calories without exceeding the limit C.
As an example, consider a limit of 40 calories and 6 buckets with 7, 13, 17, 19, 29, and 31 calories. Bessie could eat 7 + 31 = 38 calories but could eat even more by consuming three buckets: 7 + 13 + 19 = 39 calories. She can find no better combination.

输入描述

Line 1: Two space-separated integers: C and B
Line 2: B space-separated integers that respectively name the number of calories in bucket 1, 2, etc.

输出描述

Line 1: A single line with a single integer that is largest number of calories Bessie can consume and still stay on her diet.

输入

40 6
7 13 17 19 29 31

输出

39

解题思路

题意:确定饲料桶的最佳组合，使Bessie在不超过限制C的情况下获得多的卡路里。
思路:01背包。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
int w[25], dp[35005];
int main() {
    int v, n;
    scanf("%d%d", &v, &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &w[i]);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++)
        for (int j = v; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
    printf("%d\n", dp[v]);
    return 0;
}