题目名称	395. [USACO Oct09] Bessie 的体重问题
输入输出	`diet.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	16 MiB
测试数据	11
题目来源	sywgz 于2009-11-02加入
开放分组	全部用户
提交状态
分类标签	USACO 搜索法动态规划背包问题 01背包
	分享题解

通过：341，提交：581，通过率：58.69%
┭┮﹏┭┮	100	0.025 s	2.22 MiB	C++
Yuri	100	0.026 s	0.46 MiB	C++
八级大狂风	100	0.026 s	0.48 MiB	C++
Dissolute丶Tokgo	100	0.026 s	0.48 MiB	C++
Dissolute丶Mare	100	0.026 s	0.48 MiB	C++
雪狼	100	0.026 s	0.49 MiB	C++
Holiye	100	0.026 s	0.49 MiB	C++
ch3coooh	100	0.026 s	0.50 MiB	C++
ww944606393	100	0.026 s	0.50 MiB	C++
kxxy	100	0.026 s	0.95 MiB	C++

本题关联比赛
20091103
动态规划练习
叫图论的DP题

关于 Bessie 的体重问题的近10条评论(全部评论)
cb 2020-04-20 10:42 19楼
一个模板用七八次，有意思吗？夜莺 2020-02-06 15:27 18楼
WA了一次，原来是数组开小了。再次提醒：注意数据范围！ _WA自动机 2017-07-21 21:42 17楼
一A的01背包。。不知道自己是会背这种代码了还是真的理解了 kZime 2017-03-08 20:00 16楼
为了追上神犇，用一份代码水了好多题...我对不起组织... ZWOI_你猜啊 2016-11-17 11:57 15楼
Zwoi_只会打表抄代码的蒟蒻 2016-10-25 18:32 14楼
回复 @ch3coooh : 好像是。 miss dog 2016-07-30 16:24 13楼
谁给讲讲第二个数据，为啥我总是会输出65，别的都对。星眸初泛潋滟光 2016-07-21 13:42 12楼
表示和装箱问题代码一样 zeppoe 2016-06-20 14:12 11楼
zero one SOBER GOOD BOY 2016-03-19 11:23 10楼

395. [USACO Oct09] Bessie 的体重问题

★★ 输入文件：diet.in 输出文件：diet.out 简单对比
时间限制：1 s 内存限制：16 MiB

【题目描述】

Bessie像她的诸多姊妹一样，因为从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置于一个及其严格的节食计划之中。她每天不能吃多过H (5 <= H <= 45,000)公斤的干草。 Bessie只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N (1 <= N <= 500)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。给定一个列表表示每捆干草的重量S_i (1 <= S_i <= H), 求Bessie不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。

【输入格式】

* 第一行: 两个由空格隔开的整数: H 和 N

* 第2到第N+1行: 第i+1行是一个单独的整数，表示第i捆干草的重量S_i。

【输出格式】

* 第一行: 一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的干草。

【样例输入】

【样例输出】

【样例说明】

有四捆草，重量分别是15, 19, 20和21。 Bessie可以吃3捆干草（重量分别为15, 20, 21）。恰好达到她的56公斤的限制。

【来源】

USACO Oct09