时间限制：3000 ms  |  内存限制：65535 KB

难度：2

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std ;

#define Max(a,b) a>b?a:b

int dp[100020] ;

int weight[25] ;

int main ( ) {

    int n , i , j ;

    while ( ~scanf ( "%d" , &n ) ) {

        memset ( dp , 0 , sizeof(dp) ) ;

        int sum = 0 ;

        for ( i = 1 ; i <= n ; i++ ) {

            scanf ( "%d" , &weight[i] ) ;

            sum += weight[i] ;

        }

        int k = sum / 2 ;

        for ( i = 1 ; i <= n ; i++ ) {

            for ( j = k ; j >= weight[i] ; j-- ) {

                dp[j] = Max ( dp[j] , dp[j-weight[i]] + weight[i] ) ;

            //    if ( dp[j-weight[i]] + weight[i] > dp[j] )

              //       dp[j] = dp[j-weight[i]] + weight[i] ;

            }

        }

        printf ( "%d\n" , sum - 2 * dp[k] ) ;

    }

    return 0 ;

}

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

 

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（<=30）是发票张数。随后是 N 行输入，每行的格式为：
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

 

对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

 

 

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std ;

#define Max(a,b) a>b?a:b

int dp[3000020] ;

int money[1005] ;

int main ( ) {

    double s , x ;

    int n , m ,sign , ss , sum ;

    char ch ;

    while ( cin >> s >> n && n ) {

        int k = 1 ;

        ss = (int)( s * 100 ) ;

        memset ( dp , 0 , sizeof(dp) ) ;

        while ( n-- ) {

            scanf ( "%d" , &m ) ;

            getchar ( ) ;

            sum = 0 , sign = 1 ;

            while ( m-- ) {

                scanf ( " %c:%lf" , &ch , &x ) ;

                int mm = ( int ) ( x*100 ) ;

                sum += mm ;

                if ( mm > 60000 || sum > 100000 ) sign = 0 ;

                if ( ch != 'A' && ch != 'B' && ch != 'C' ) sign = 0 ;

     //           printf ( " mm = %d sum = %d sign = %d \n" , mm , sum , sign ) ;

            }

            if ( sign ) money[k++] = sum ;

        }

  //      printf ( " ss = %d sum = %d " , ss , sum ) ;

 //      for ( int i = 1 ; i < k ; i++ ) cout << money[i] << '\t' ;

        for ( int i = 1 ; i < k ; i++ ) {

            for ( int j = ss ; j >= money[i] ; j-- ) {

                dp[j] = Max ( dp[j] , dp[j-money[i]]+money[i] ) ;

  //              cout << dp[j] ;

            }

    //        cout << '\n' ;

        }

        printf ( "%.2f\n" , dp[ss] / 100.0 ) ;

    }

    return 0 ;

}