题解 | The Eating-牛客假日团队赛5E题

E-The Eating Puzzle_牛客假日团队赛5

https://ac.nowcoder.com/acm/contest/984/E

题目描述

Bessie is on a diet where she can eat no more than calories per day. Farmer John is teasing her by putting out 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.

示例1

输入
40 6
7 13 17 19 29 31
输出
39

解答

注意dp数组的初始化,状态方程:

for i=1..N

    forv=V..0

       f[v]=max{f[v],f[v-c[i]]+w[i]};

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
    int V,n;
    int w[25],dp[35005];
    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;
}

来源:Mizersy
全部评论

相关推荐

头像
02-15 16:23
中南大学 Java
野猪不是猪🐗:签了美团真是不一样! 亲戚们都知道我签了美团,过年都围着我问送一单多少钱,还让弟弟妹妹们引以为戒,笑我爸我妈养了个🐢孩子,说从小就知道我这个人以后肯定没出息,我被骂的都快上天了
点赞 评论 收藏
分享
客户端劝退第六人:情根深种啊,想让你回心转意
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务