poj 3628 Bookshelf 2 01背包

//f[i]表示能达到i高度的由牛组成的最小高度
//f[i] = min(f[i], f[i - h] + h)  h <= i <= b
//       min(f[i], h)			0 <= i < h
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int f[120001];
int n, b;
int data[6];
int main() {
	freopen("1.txt", "r", stdin);
	while(cin >> n >> b) {
		for(int i = 0; i <= b; i++)
			f[i] = 20000000;
		f[0] = 0;
		for(int i = 0; i < n; i++) {
			int h;
			cin >> h;
			for(int j = b; j >= h; j--) {
				f[j] = min(f[j], f[j - h] + h);
			}
			for(int j = h - 1; j >= 0; j--)
				f[j] = min(h, f[j]);
		}
		cout << f[b] - b << endl;
	}
 	return 0;
}