POJ3628 Bookshelf 2(01背包)

题意：

你要很多不同高度的奶牛，想要达到一个高度为b的书架，将奶牛一个个叠起来，要求奶牛的高度和大于b，输出大于b且最小的高度和

要点：

将所有奶牛高度都加起来减去b的值作为背包大小，这样便转化成一个比较普通的01背包问题。现在就是等于向背包里放奶牛，使得高度和最大，这样与b的差值就会越小。这题稍微有点不同，只有一个高度值，原本是有一个价值一个重量两个值，但其实是一样的，最终都是讨论当前这个奶牛放入还是不放入的问题，只不过这里价值与高度值看成相同罢了

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a,b) a>b?a:b
int dp[20000000];int main()
{int n, b;int h[25];while (scanf("%d%d", &n, &b) != EOF){int sum = 0;for (int i = 1; i <= n; i++){scanf("%d", &h[i]);sum += h[i];}int v = sum - b;//相当于奶牛总高度-书架高度=背包大小的背包问题求最大值for (int i = 1; i <= n; i++)for (int j = v; j >= h[i]; j--)dp[j] = max(dp[j], dp[j - h[i]] + h[i]);//这里背包的变种，但根本还是放和不放的问题，只不过重量和价值变成同一个了printf("%d\n", v - dp[v]);//最后输出差值}return 0;
}