【题目描述：】

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草． 顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

【输入格式：】

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

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

【输出格式：】

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

[算法分析：]

一看就是01背包，但是交上板子以后TLE了，加了炒鸡快读才刚好1000ms卡过

于是考虑优化算法：

类似于搜索的剪枝，对f[j]进行处理的时候，如果f[j]=c（最大容量）了，那输出c直接结束程序。

• 优化前：1000ms

• 优化后：108ms
  
  
  

[Code:]

#include<iostream>

#include<cstdio>

#define re register

using namespace std;

const int MAXN = 5000 + 1;

const int MAXC = 50000 + 1;

int n, c, v[MAXN];

int f[MAXC];

inline char gc()

{

    static char buff[1000000],*S=buff,*T=buff;

    return S==T&&(T=(S=buff)+fread(buff,1,1000000,stdin),S==T)?EOF:*S++;

}

inline int read() {

	int x = 0; char ch = gc();

	while(!isdigit(ch)) ch = gc();

	while(isdigit(ch))

		x = (x << 3) + (x << 1) + ch - 48, ch = gc();

	return x;

}

int main() {

	c = read(), n = read();

	for(re int i=1; i<=n; ++i)

		v[i] = read();

	for(re int i=1; i<=n; ++i)

		for(re int j=c; j>=v[i]; --j) {

			f[j] = max(f[j], f[j-v[i]]+v[i]);

			if(f[j] == c) {

				printf("%d", c);

				return 0;

			}

		}

	printf("%d", f[c]);

}