HDU-1864-最大清算額【01リュック】

HDU-1864-最大償還額

        Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Descriptionの既存の経費は一定額の領収書を清算することができます.請求書の償還を許可するタイプには、図書(A類)、文房具(B類)、出張(C類)が含まれており、請求書1枚あたりの総額は1000元を超えてはならず、請求書1枚あたりの単品の価値は600元を超えてはならない.提供された請求書の山の中で償還可能な、所定額を超えない最大の償還額を見つけるプログラムを作成してください.
Inputテスト入力には、いくつかのテスト例が含まれています.各テストケースの1行目には、Qが所定の償還額である2つの正数QおよびNが含まれる.N(<=30)は、請求書枚数です.次に、N行入力です.各行の形式は、m Type_1:price_1 Type_2:price_2…Type_m:price_mのうち正の整数mは、この請求書に書かれている品目の件数で、Type_iとprice_iは、i番目の品目の種類と価値です.品目の種類は、大文字と英字で表されます.Nが0の場合、すべての入力が終了し、対応する結果は不要です出力します.
Outputは、各テスト・インスタンスに対して1行を出力します.すなわち、清算可能な最大額は、小数点以下2桁まで正確です.
Sample Input 200.00 3 2 A:23.50 B:100.00 1 C:650.00 3 A:59.99 A:120.00 X:10.00 1200.00 2 2 B:600.00 A:400.00 1 C:200.50 1200.50 3 2 B:600.00 A:400.00 1 C:200.50 1 A:100.00 100.00 0
Sample Output 123.50 1000.00 1200.50
タイトルリンク:HDU-1864
テーマ構想:01リュック、しかし値が浮動小数点数なため

        ：dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1] + ans[i]); //i：      i   ,j    j   ,dp  ， j      ，       

コードは次のとおりです.

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
#define EPS 1e-6
double dp[40][40];
int main(){
    double q;
    int n;
    while(cin >> q >> n && n)
    {
        memset(dp,0,sizeof(dp));
        vector <double> ans;
        ans.push_back(0);
        for (int i = 0; i < n; i++)
        {
            int m;
            cin >> m;
            double sum = 0,A = 0,B = 0,C = 0;
            int flag = 1;
            while(m--)
            {
                char a,b;
                double num;
                cin >> a >> b >> num;
                flag = 1;
                if (num > 600) flag = 0;
                if (a == 'A') A += num;
                if (a == 'B') B += num;
                if (a == 'C') C += num;
                if (a != 'A' && a != 'B' && a != 'C') flag = 0;
                if (A > 600 || B > 600 || C > 600) flag = 0;
                sum += num;
            }
            if (sum > 1000) flag = 0;
            if (flag) ans.push_back(sum);
        }
        int len = ans.size();
        double last = 0;
        for (int i = 1; i <= len; i++)
        {
            for (int j = 1; j <= i; j++)
            {
            // if (dp[i - 1][j - 1] + ans[i] <= q) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1] + ans[i]);
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1] + ans[i]);
                if (dp[i][j] - q <= EPS)    last = max(dp[i][j],last);
            }
        }       
        printf("%.2f
",last);
    } 
    return 0;
}