DP：poj 3628 Bookshelf 2（ 0-1背包）
【转】http://blog.csdn.net/zxy_snow/article/details/6052676
?
这个相当于体积和价值一样大的01背包。
?
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int w[1000002],bag[20000005];
int main(void)
{
?int n,c;
?while( scanf("%d %d",&n,&c)!=EOF? )
?{
??int sum = 0;
??for(int i=1; i<=n; i++)
??{
???scanf("%d",&w[i]);
???sum += w[i];
??}
??for(int i=1; i<=c; i++)
???bag[i] = 0;
??for(int i=1; i<=n; i++)
???for(int k=sum; k>=w[i]; k--)
???{
????if( bag[k] < bag[k-w[i]] + w[i] )
?????bag[k] = bag[k-w[i]] + w[i];
???}
??int min = INT_MAX;
??for(int i=c; i<=sum; i++)
??{
???if( bag[i] >= c && bag[i] - c < min )
????min = bag[i] - c;
??}
??cout << min << endl;
?}
return 0;
}
