題意：給定n個(gè)數(shù)，要求從這n個(gè)數(shù)中的選取一些數(shù)和sum大于指定數(shù)b，要求sum-b最小。
解法：剛開(kāi)始可以把所有n個(gè)數(shù)全部相加得到sum，sum肯定大于b，令m=sum-b,要盡量在這m中多的減去原來(lái)在sum中的數(shù)，使得m最小；
即從這n個(gè)數(shù)種選取幾個(gè)數(shù)，使得在其和不超過(guò)m的情況下最大,這不就是一個(gè)01背包問(wèn)題么。解之。
#include <stdio.h>
#include <string.h>
#define N 1000005
#define MAX(a, b)(a > b ? a : b)
int v[N], h[25];
int main()
{
int n, b, sum = 0;
scanf("%d %d", &n, &b);
for(int i = 0; i < n; i++)
{
scanf("%d", &h[i]);
sum += h[i];
}
b = sum - b;
for(int i = 0; i < n; i++)
for(int j = b; j >= h[i]; j--)
{
v[j] = MAX(v[j], v[j - h[i]] + h[i]);
}
printf("%d\n", b - v[b]);
return 0;
}