P2639 [USACO09OCT]Bessie的體重問題Bessie's We…

題目描述

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在限制範圍內最多可以吃多少公斤的乾草。

輸入輸出樣例

56 4
15
19
20
21

56

說明

輸入說明:

有四捆草，重量分別是15, 19, 20和21。Bessie在56公斤的限制範圍內想要吃多少就可以吃多少。

輸出說明:

Bessie可以吃3捆乾草（重量分別為15, 20, 21）。恰好達到她的56公斤的限制。

將讀入的數x

看做一個重量為x，價值為x的物品

跑背包

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 void read(int & n)
 7 {
 8     char c='+';int x=0;int flag=0;
 9     while(c<'0'||c>'9')
10     {
11         c=getchar();
12         if(c=='-')
13         flag=1;
14     }
15     while(c>='0'&&c<='9')
16     x=x*10+(c-48),c=getchar();
17     flag==1?n=-x:n=x;
18 }
19 const int MAXN=100001;
20 int maxt,n;
21 int dp[MAXN];
22 int a[501];
23 int main()
24 {
25     read(maxt);read(n);
26     for(int i=1;i<=n;i++)
27         read(a[i]);
28     for(int i=1;i<=n;i++)
29     {
30         for(int j=maxt;j>=0;j--)
31         {
32             if(a[i]<=j)
33             dp[j]=max(dp[j],
34                       dp[j-a[i]]+a[i]);
35             else
36             dp[j]=dp[j];
37         }    
38     }
39     cout<<dp[maxt];
40     return 0;
41 }