http://poj.org/problem?id=3628
题意：给出一个高度H和n个牛的高度，要求把牛堆叠起来达到H，求出该高度和H的最小差。
思路：首先我们计算出牛的总高度sum，sum-H就相当于一个背包容量，如果我们往里装高度正好等于了sum-H，也就是说明我们堆叠的牛的高度正好等于了H。
这样一来很好理解，就是计算在一个背包容量为sum-H的背包中最多能装多少。题目本身还是不难的，直接套用模板就行了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 1000000+5; 7 8 int n, h; 9 int dp[maxn]; 10 int sum; 11 12 int w[maxn]; 13 14 int main() 15 { 16 //freopen("D:\\txt.txt", "r", stdin); 17 while (cin >> n >> h && n && h) 18 { 19 //memset(dp, 0, sizeof(dp)); 20 sum = 0; 21 for (int i = 1; i <= n; i++) 22 { 23 cin >> w[i]; 24 sum += w[i]; 25 } 26 int x = sum - h; 27 for (int i = 1; i <= n; i++) 28 { 29 for (int j = x; j >= w[i]; j--) 30 dp[j] = max(dp[j], dp[j - w[i]] + w[i]); 31 } 32 cout << x-dp[x] << endl; 33 } 34 return 0; 35 }
原文：http://www.cnblogs.com/zyb993963526/p/6361510.html