【题目描述：】
约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为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
#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]);
}【洛谷】【动态规划/01背包】P2925 [USACO08DEC]干草出售Hay For Sale
原文：https://www.cnblogs.com/devilk-sjj/p/9210829.html