EOJ2466. Hay For Sale

Farmer John suffered a terrible loss when giant Australian cockroaches ate the entirety of his hay inventory, leaving him with nothing to feed the cows. He hitched up his wagon with capacity C (1 <= C <= 50,000) cubic units and sauntered over to Farmer Don’s to get some hay before the cows miss a meal.

Farmer Don had a wide variety of H (1 <= H <= 5,000) hay bales for sale, each with its own volume (1 <= V_i <= C). Bales of hay, you know, are somewhat flexible and can be jammed into the oddest of spaces in a wagon.

FJ carefully evaluates the volumes so that he can figure out the largest amount of hay he can purchase for his cows.

Given the volume constraint and a list of bales to buy, what is the greatest volume of hay FJ can purchase? He can’t purchase partial bales, of course. Each input line (after the first) lists a single bale FJ can buy.

input

Line 1: Two space-separated integers: C and H

Lines 2..H+1: Each line describes the volume of a single bale: V_i

7 3
2
6
5
INPUT DETAILS:
The wagon holds 7 volumetric units; three bales are offered for sale with
volumes of 2, 6, and 5 units, respectively.

output

Line 1: A single integer which is the greatest volume of hay FJ can
purchase given the list of bales for sale and constraints.

7
OUTPUT DETAILS:
Buying the two smaller bales fills the wagon.

code

文章大意：

当澳大利亚巨大的蟑螂吃掉了全部干草时，农夫约翰遭受了惨重的损失，这使他没有什么可养牛的。他用容量为C（1 <= C <= 50,000）立方单位的货车搭便车，然后走到农夫唐氏那里，在母牛错过一顿饭之前放些干草。

农夫唐出售各种H（1 <= H <= 5,000）干草，每捆都有自己的体积（1 <= V_i <= C）。您知道，大包的干草有些柔韧性好，可以塞在马车上最奇怪的空间中。

FJ会仔细评估其体积，以便能够找出可为母牛购买的最大干草量。

给定数量限制和要购买的捆包清单，最大可以购买的干草FJ量是多少？当然，他不能购买部分大包。每个输入行（在第一行之后）列出FJ可以购买的单个草捆

#include<iostream>
using namespace std;
const int MAX=50000+10;
int c[MAX],h[MAX];
int f[MAX];//背包体积为n时的最大体积利用数 
int n,m;//n--背包体积 m--个数 
int main(){
    cin>>n>>m;
   for(int i=1;i<=m;i++){
       cin>>h[i];
   }
   for(int i=1;i<=m;i++){//看是否能装下第i个，能装下就更新f,不能就换下一个i 
       for(int j=n;j>=h[i];j--){
           f[j]=max(f[j],f[j-h[i]]+h[i]);//要么不装h[i],要么装h[i] ，两者取最大 
       }
   }
    cout<<f[n];
    
    return 0;
}