http://poj.org/problem?id=3628
题意:
有N条牛,每条牛的的高度为Hi,有一个书架高度为B,求一些牛叠起来的高度与B的最小高度差。
有点变化的01背包~~~
code:
#include <stdio.h> #include <string.h> #define N 20000005 int a[25]; int f[N]; int main() { int n, m, i, j, max; while(~scanf("%d%d",&n,&m)) { max = 0; for(i=0; i<n; i++) { scanf("%d",&a[i]); if(max<a[i]) max = a[i];} for(i=1; i<=m+max; f[i]=0,i++); f[0] = 1; for(i=0; i<n; i++) for(j=m+max; j>=a[i]; j--) if(f[j-a[i]]) f[j] = 1; for(i=m; i<=m+max; i++) if(f[i]) { printf("%d\n",i-m); break; } } return 0; }