HDU_최대 청구 액 (DP)

최대 결산 액
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 17519 Accepted Submission(s): 5137
Problem Description
현재 경 비 는 일정 한도 의 영수증 을 결산 할 수 있다.청구 가 허 용 된 영수증 유형 은 도서 구입 (A 종), 문구 (B 종), 출장 (C 종) 을 포함 하 며, 영수증 한 장 당 총액 이 1 천원 을 초과 해 서 는 안 되 며, 영수증 한 장 당 단일 물품 의 가 치 는 600 원 을 초과 해 서 는 안 된다.지금 프로그램 을 작성 하여 제 시 된 영수증 더미 에서 청구 할 수 있 는, 주어진 금액 을 초과 하지 않 는 최대 청구 액 을 찾 아 보 세 요.

Input
테스트 입력 은 약간의 테스트 용례 를 포함한다.각 테스트 용례 의 첫 줄 에는 두 개의 정수 Q 와 N 이 포함 되 어 있 으 며, 그 중에서 Q 는 주어진 결산 한도 이 고, N (< = 30) 은 영수증 장수 이다.다음은 N 줄 입력 입 니 다. 각 줄 의 형식 은 다음 과 같 습 니 다.
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
그 중 정수 m 는 이 영수증 에 열 린 물품 의 개수 입 니 다. Typei 와 pricei 는 제 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

题解：题目的输入比较麻烦。在判断是否为合法发票的前提下，很容易能看出这道题属于01背包。

因为报销额为double型，所以我们对每张发票是否放入进行dp。递推公式为：dp[i]=max(dp[i],dp[i-1]+sum),sum=Ai+Bi+Ci;

或者所有参数*100，转换成最基本的01背包，但是时间复杂度会高一些。

思考：

最开始的时候是看别人的代码，才写出了dp函数的循环递推，但是根本没有理解。后来在做到类似的题目才反过来看，却又看不懂了，debug了很久才发现自己最开始的理解就是错的。这个方法其实是很有贪心的意思，我们先从定义开始慢慢理解。

dp[i]:报销i张发票得到的最大报销额。（注意是报销i张，而没有强调是第i张或前i张，有从N张中挑i张得到最大值的意思）

外层循环：从0~n-1将n张发票代入，以此尝试更新dp数组。

内层循环:这里是最迷惑人的，因为普通的01内层确实是倒序，为了保证某件物品只可能被放入一次。但是关键那样内层循环应从MAX~0，MAX表示发票总额能达到的最大值，而这道题因为是double类型，这是无法实现的(不扩大100倍的话)。在下面代码中我们从N~1倒序遍历，在避免了多次放入的同时，dp数组从N到1逐个尝试更新，每次都保证我们存储的是当报销1,2...j...N张时的最大值。依据贪心思想得到最终报销N张能得到的最大值。递推式dp[i]=max(dp[i],dp[j]+sum[i](1<=j<=N));经过认真地思考得到的知识更让我感到珍惜。。

附代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAX_N 40
using namespace std;

double l[MAX_N][5];
int show[MAX_N];//    map           
double dp[MAX_N];//    i             
map ml;//  ABC 012
int main()
{
    double Q;
    int N,m;
    double result;
    bool flag;
    while( scanf("%lf%d",&Q,&N) != EOF && N )
    {
        memset(l,0,sizeof(l));
        memset(show,0,sizeof(show));
        memset(dp,0,sizeof(dp));
        ml['A']=0;
        ml['B']=1;
        ml['C']=2;
        for( int i = 0; i < N; i++ )
        {
            scanf("%d",&m);
            flag=true;
            for( int j = 0; j < m; j++ )
            {
                char c;double x;
                scanf(" %c:%lf",&c,&x);//  
                if( (c!='A'&&c!='B'&&c!='C') || x > 600)
                {
                    flag=false;
                    continue;
                }
                l[i][ml[c]]+=x;
            }
            //          A       ，          
            if( flag && l[i][0]+l[i][1]+l[i][2] <= 1000 && l[i][0]<=600 && l[i][1]<=600 && l[i][2]<=600 )
                show[i]=1;
        }
        result=0;
        for( int i = 0; i < N; i++ )
        {
            double sum=0;
            if( show[i] == 1 )
                sum=l[i][0]+l[i][1]+l[i][2];
            //    
            for( int j = N; j >= 1; j-- )
            {        
   				if( j == 1 || (dp[j-1]>0&&dp[j-1]+sum<=Q) )
                      dp[j]=max(dp[j],dp[j-1]+sum);
                result=max(result,dp[j]);
            }
        }
        printf("%.2lf
",result);
    }
    return 0;
}

 
  
 
   
     N<=30，    dfs         。 
   
   
       dfs   ： 
   #include 
#include 
#include 
#include 
#include 
using namespace std;
double total, one, kind[3], ans;
int N, item, vlen;
char type;
bool useless;
std::vector v;
std::hash_map  vis;

void dfs(int k, double sum) {
    //    
    if(ans == total || vis[sum]) return ;
    vis[sum] = true;
    if(sum > ans) {
        ans = sum;
    }
    for (int i = k; i < vlen; i ++){
        if(sum + v[i] <= total){
            dfs(i+1, sum + v[i]);
        } else break;
    }
}
int main() {
    while(scanf("%lf%d", &total, &N) != EOF, N) {
        v.clear();
        for (int i = 0; i < N; i ++) {
            scanf("%d", &item);
            useless = false;
            kind[0]  = kind[1] = kind[2]= 0;
            while(item --) {
                scanf(" %c:%lf", &type, &one);
                if(useless == true) continue;
                if(type > 'C' || kind[type- 'A'] + one  > 600) {
                    useless = true;
                }
                kind[type-'A'] += one;
                if(kind[0] + kind[1] + kind[2] > 1000) {
                    useless = true;
                }
            }
            if(useless == false) {
                v.push_back(kind[0] + kind[1] + kind[2]);
            }
        }
        vlen = v.size(), ans = 0;
        vis.clear();
        //         ，        ，   sum     
        //  ,              
        std::sort(v.begin(), v.end());
        dfs(0, 0);
        printf("%.2lf
", ans);
    }
    return 0;
}
  
첨부 코드:

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

124. 두 갈래 나무의 최대 경로와 leetcode

비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU_최대 청구 액 (DP)

좋은 웹페이지 즐겨찾기