饭卡

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

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

Input

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

n=0表示数据结束。

Output

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

Sample Input

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

Sample Output

-45 32

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std ;
 5 
 6 int main () {
 7     //freopen ("a.txt" , "r" , stdin) ;
 8     int dish[1005] , n ;
 9     int dp[2000] ;
10     int bal ;
11     while (scanf("%d" , &n ) != EOF ) {
12         if ( !n )
13            break ;
14         for (int i = 0 ; i < n ; i++ ) {
15             scanf ("%d" , &dish[i] ) ;
16         }
17         scanf ("%d" , &bal ) ;
18         sort ( dish , dish + n ) ;
19         memset ( dp , 0 , sizeof(dp) ) ;
20 
21         if ( bal >= 5 )
22             dp[bal + 100 ] = 1 ;
23         else {
24             printf ("%d
" , bal ) ;
25             continue ;
26         }
27         for (int i = 0 ; i < n ; i++ ) {
28             for (int j = 105 ; j <= bal + 100 ; j++ ) {
29                 if ( dp[j] ) {
30                     dp[j - dish[i]] = 1 ;
31                 }
32             }
33         }
34         for (int i = 0 ; i <= bal + 100; i++ )
35             if ( dp[i] ) {
36                 printf("%d
" , i - 100 );
37                 break ;
38             }
39     }
40     return 0 ;
41 }

01背包

dp前一定要对 dish[n] 进行排序，不然会错。

=。= 虽然还没搞清为啥。