HDU 2546饭卡

http://acm.hdu.edu.cn/showproblem.php?pid=2546

通过题目的讲解我们大致上得到以下思路：

先排一个序，或者直接找到最大值，将最大值取出，在剩余的n-1个数中，找到一个组合，使得他们的和尽量接近m-5，找到后用m减去这个数和最大数，就可以求出最大的负值。

所以，该问题隐藏着一个经典的问题：从n个数中选m个使得他们的和尽可能的接近x

这个问题非常简洁，但是各大公司都喜欢考，搜狐面试，搜狗笔试都考过这个题。

那么如何解决呢？

因为尽量接近x所以想到了背包的容量，如果有一个背包的容量为x向其中加入n个物品，物品的价值和体积看成一样，这样的话，体积不会超过m，而与之等值的价值取到最大，这不就是最接近x吗？

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 #define M 1100
 7 #define mem0(f) memset(f,0,sizeof(f))
 8 int dp[M];
 9 int t,n,v,m;
10 int val[M];
11 int solve()
12 {
13     for(int i=0;i<n-1;i++)
14     {
15         for(int k=m-5;k>=val[i];k--)
16         {
17             dp[k]=max(dp[k],dp[k-val[i]]+val[i]);
18         }
19     }
20     return dp[m-5];
21 }
22 int main()
23 {
24     while(~scanf("%d",&n)&&n)
25     {
26         mem0(val);
27         mem0(dp);
28         for(int i=0;i<n;i++)
29             scanf("%d",&val[i]);
30         sort(val,val+n);
31         scanf("%d",&m);
32         int cc=solve();
33         if(m<5)printf("%d
",m);
34         else
35         printf("%d
",m-cc-val[n-1]);
36     }
37     return 0;
38 }