
http://poj.org/problem?id=3628
题意:给出一个高度H和n个牛的高度,要求把牛堆叠起来达到H,求出该高度和H的最小差。
思路:首先我们计算出牛的总高度sum,sum-H就相当于一个背包容量,如果我们往里装高度正好等于了sum-H,也就是说明我们堆叠的牛的高度正好等于了H。
这样一来很好理解,就是计算在一个背包容量为sum-H的背包中最多能装多少。题目本身还是不难的,直接套用模板就行了。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std; const int maxn = +; int n, h;
int dp[maxn];
int sum; int w[maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
while (cin >> n >> h && n && h)
{
//memset(dp, 0, sizeof(dp));
sum = ;
for (int i = ; i <= n; i++)
{
cin >> w[i];
sum += w[i];
}
int x = sum - h;
for (int i = ; i <= n; i++)
{
for (int j = x; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
cout << x-dp[x] << endl;
}
return ;
}