hdu 2546 饭卡-动态规划-[解题报告]C++ | Acm之家

hdu 2546 饭卡-动态规划-[解题报告]C++ | Acm之家

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

输入:

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。

输出:

多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。

样例输入:

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0



 

Sample Output


-45
32

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

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

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

那么如何解决呢？

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

http://www.cnblogs.com/plank-george-zzo/archive/2013/08/14/3256720.html

 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\n",m);
34         else
35         printf("%d\n",m-cc-val[n-1]);
36     }
37     return 0;
38 }

http://mangogao.com/read/298.html

因为5元以上可以购买任意物品，因此需要用这5元来购买最贵的物品。因此问题转化为怎样购买物品，使得花费最高且不超过m-5。每个物品最多选择1次，属于01背包问题。

利用滚动数组，对于i从0~n-2，dp[j]表示前i个物品放入容量为j的背包的最大价值。
则第i个物品不取时，继承上一轮结果，dp[j]=dp[j];
第i个物品取时，取最大值，j-a[i]容量的背包中放入a[i]， dp[j] = max{dp[j], dp[j-a[i]] + a[

const int maxn = 1010;
int a[maxn], dp[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    int n, m;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++)
            cin >> a[i];
        cin >> m;
        if (m < 5) {
            cout << m << endl;
            continue;
        }
        sort(a, a + n);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n - 1; i++)
            for (int j = m - 5; j >= a[i]; j--)
                dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        cout << m - dp[m - 5] - a[n - 1] << endl;
    }

    return 0;
}
Read full article from hdu 2546 饭卡-动态规划-[解题报告]C++ | Acm之家