BZOJ 3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 背包dp

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题

Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 147  Solved: 131 [Submit][Status][Discuss]

Description

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

Input

    第1行：两个由空格隔开的整数日和N.     第2到第N+1行：第i+l行是一个单独的整数，表示第i捆干草的重量Si．

Output

    一个单独的整数表示贝茜在限制范围内最多可以吃多少公斤的干草．

Sample Input

56 4 15 19 20 21

Sample Output

56

HINT

    有四捆草，重量分别是15，19，20和21.贝茜在56公斤的限制范围内想要吃多少就可以吃多少．

    贝茜可以吃3捆干草（重量分别为15，20，21）．恰好达到她的56公斤的限制．

你当我会告诉你 我第一眼没看出来是背包吗

#include<cmath> #include<ctime> #include<cstdio> #include<cstdlib> #include<cstring> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f*x; } inline void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=45100; int a[N],f[N]; int main() { int m=read(),n=read(); register int i,j; for(i=1;i<=n;++i)a[i]=read(); for(i=1;i<=n;++i) for(j=m;j>=a[i];j--)f[j]=max(f[j],f[j-a[i]]+a[i]); print(f[m]);puts("");return 0; } /* 56 4 15 19 20 21 56 */