【 POJ - 3628 】Bookshelf 2（dfs 或 dp，0-1背包）

题干：

Farmer John recently bought another bookshelf for the cow library, but the shelf is getting filled up quite quickly, and now the only available space is at the top.

FJ has N cows (1 ≤ N ≤ 20) each with some height of Hi (1 ≤ Hi ≤ 1,000,000 - these are very tall cows). The bookshelf has a height of B (1 ≤ B ≤ S, where S is the sum of the heights of all cows).

To reach the top of the bookshelf, one or more of the cows can stand on top of each other in a stack, so that their total height is the sum of each of their individual heights. This total height must be no less than the height of the bookshelf in order for the cows to reach the top.

Since a taller stack of cows than necessary can be dangerous, your job is to find the set of cows that produces a stack of the smallest height possible such that the stack can reach the bookshelf. Your program should print the minimal 'excess' height between the optimal stack of cows and the bookshelf.

Input

* Line 1: Two space-separated integers: N and B
* Lines 2..N+1: Line i+1 contains a single integer: Hi

Output

* Line 1: A single integer representing the (non-negative) difference between the total height of the optimal set of cows and the height of the shelf.

Sample Input

5 16
3
1
3
5
6

Sample Output

1

题目大意：

    其实很简单啦就是给你n个高度，让你挑其中的几个摞起来。要求摞起来以后的总高度超过b，问你这样的高度的最小值是多少。（让你输出  最小值 - b ）

有n头牛，已知每头牛的高度和书架高度，一头牛可以站在另一头牛身上，总高度是他们的高度之和。要求能够达到书架的顶端，即这些牛的总高度不低于书架高度，求满足条件的总高度的最小值，输出他们的差值。

解题报告：

    这题高度小于100W(1e6)，但是题目说b要小于总高度和，n<=20，也就是说b<=2000W(2e7)，这个数字其实做0-1背包就已经很牵强了（我也试过了开了2e7的数组然后MLE了），不过还好这题数据量没给到这么大，开个100W的数组就过去了。不过要说到正解，这题是搜索啊！n<=20这么小的数据量你不去dfs吗？！

下面附四个代码：

AC代码1：（自己写  装满类型0-1背包）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int MAX = 1000000 +5;
const int INF = 0x3f3f3f3f;
int dp[MAX];
int v[50];

bool cmp(const int a,const int b) {
    return a>b;
}
int main()
{
    int n,b;
    cin>>n>>b;
    for(int i = 1; i<=n; i++) {
        cin>>v[i];
    }
    sort(v+1,v+n+1,cmp);//cout <<"kaishile"<<endl;
    memset(dp,INF,sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i<=n; i++) {
        for(int j = b + v[1]; j>=v[i]; j-- ) {
            dp[j] = min(dp[j],dp[j -v[i] ] + 1);
        }
    }

    int ans = -1;
    for(int i = b; i<=b+v[1]; i++) {
        if(dp[i] !=INF) {
            ans = i - b; break;
        }
    }
    cout << ans<<endl;
    return 0 ;
}

AC代码2：（网络版的 装满类型0-1背包） 

#include<cstdio>
using namespace std;
const int mm=20000000;
bool f[mm];
int h[22];
int i,j,k,n,b,m;
int main()
{
    while(scanf("%d%d",&n,&b)!=-1)
    {
        for(m=i=0;i<n;++i)scanf("%d",&h[i]),m+=h[i];
        for(i=0;i<=m;++i)f[i]=0;
        f[0]=1;
        for(i=0;i<n;++i)
            for(j=m-h[i];j>=0;--j)
                if(f[j])f[j+h[i]]=1;
        for(i=b;i<=m;++i)
            if(f[i])break;
        printf("%d\n",i-b);
    }
    return 0;
}

上面这个代码看起来0-1背包不太一样，其实是一样的。只不过一般j从m开始递减，这里是从m-h[i]开始的，其实是一样的。

之所以要把这个代码贴上来其实主要不是这个地方，而是他只用了bool类型的dp数组，因为这里只需要记录这个高度是否可以到达，而不需要知道具体能到达的高度是多少。其实往深里讲，这是因为这个题只有h[i] 这一个权值，而不是标准的0-1背包还需要w和v两个权值，所以其实就算是按照我上面自己写的代码那样写，其实每个dp数组中只要不是-INF，那么这个值一定就是高度一定就是i（也就是dp[i]一定等于i），所以其实这两种写法是等价的。

AC代码3：（纯裸的0-1背包）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[2000002], h[22];
int main()
{
    int n, m, i, j;
    while(~scanf("%d%d",&n,&m))
    {
        int sum = 0;
        memset(dp,0,sizeof(dp));
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&h[i]);
            sum += h[i];
        }
        for(i = 1; i <= n; i++)
            for(j = sum; j >= h[i]; j--)
                dp[j] = max(dp[j], dp[j - h[i]] + h[i]);
        int Min = sum;
        for(i = m; i <= sum; i++)
            if(dp[i] >= m && dp[i] - m < Min)
                Min = dp[i] - m;
        printf("%d\n",Min);
    }
    return 0;
}

AC代码4：（网络版 dfs）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int h[22], ans, flag;
int n, m;
void dfs(int k, int s)
{
	if(s == m)
	{
		ans = 0;
		return ;
	}
	if(s >= m)
	{
		if(s - m < ans)
			ans = s - m;
		return ;
	}
	for(int i = k; i < n; i++)
	{
		dfs(i+1,s+h[i]);
	}
}
int main()
{
	int i;
	while(cin >> n >> m)
	{
		int sum = 0;
		flag = 0;
		for(i = 0; i < n; i++)
		{
			cin >> h[i];
			sum += h[i];
		}
		if(sum == m)
		{
			cout << "0" << endl;
			continue;
		}
		ans = sum;
		dfs(0,0);
		cout << ans << endl;
	}
	return 0;
}