首页 > ACM题库 > 九度OJ > 九度-1025-最大报销额[解题代码]
2013
12-12

九度-1025-最大报销额[解题代码]

题目来源:2007年浙江大学计算机及软件工程研究生机试真题

题目描述:
    现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书(A类)、文具(B类)、差旅(C类),要求每张发票的总额不得超过1000元,每张发票上,单项物品的价值不得超过600元。现请你编写程序,在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
输入:
    测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N,其中 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时,全部输入结束,相应的结果不要输出。
输出:
    对每个测试用例输出1行,即可以报销的最大数额,精确到小数点后2位。
样例输入:
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
样例输出:
123.50
1000.00
1200.50

cpp 代码如下:
#include "iostream"  
#include "stdio.h"  
#include "math.h"  
#include "vector"  
#include "queue"  
#include "memory.h"  
#include "algorithm"  
#include "string"  
using namespace std;  
#define max(a,b) a>b?a:b

int bill[35];
int dp[31*1000*100];

int main()
{
	double maxx;
	int n;
	while(scanf("%lf%d",&maxx,&n)!=EOF&&n)
	{
		int i,j,m,count=0;
		double tmp,item[3],sum;
		char type;
		maxx=(int)(maxx*100);

		for(i=0;i<n;i++)
		{
            item[0]=item[1]=item[2]=0;
            sum=0;
			scanf("%d",&m);
			bool flag=true;//feasible
			sum=0;
			for(j=0;j<m;j++)
			{
				getchar();
				type=getchar();
				scanf(":%lf",&tmp);
				if(type=='A'||type=='B'||type=='C')
				{
                   item[type-'A']+=tmp;
                   sum+=tmp;
                }
				else
					flag=false;
			}
			if(flag&&sum<=1000&&item[0]<=600&&item[1]<=600&&item[2]<=600)
				bill[++count]=(int)(sum*100); 
		}

		for(i=0;i<=maxx;i++)
			dp[i]=0;

		for(i=1;i<=count;i++)
			//for(j=0;j<=(int)maxx;j++);       ==这样的话物品就可以多次选择了
			for(j=(int)maxx;j>=bill[i];j--)    //==说明每张发票(物品)只有一件
			{
				if(j>=bill[i])
					dp[j]=max(dp[j],dp[j-bill[i]]+bill[i]);
			}

			printf("%.2lf\n",1.0*dp[(int)maxx]/100);
	}
}

/**************************************************************
	Problem: 1025
	User: coder
	Language: C++
	Result: Accepted
	Time:20 ms
	Memory:13628 kb
****************************************************************/

java 代码如下:

import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Scanner;

public class Main{
	static float max;
	static int n;
	static float arr[];
	static HashMap<Float, Float> map ;
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextFloat()){
			max = s.nextFloat();
			n = s.nextInt();
			if(n==0)
				break;
			map = new HashMap<Float, Float>();
			arr = new float[n];
			for(int i=0; i<n; i++){
				int k = s.nextInt();
				int tag = 0;
				for(int j=0; j<k; j++){
					String str = s.next();
					char c = str.charAt(0);
					float temp = Float.parseFloat(str.substring(2));
					if(c=='A' || c=='B' || c=='C')
						arr[i]+= temp;
					else
						tag = 1;
				}
				if(tag == 1)
					arr[i] = 0;
			}
			System.out.printf("%.2f\n", f(max,0));
		}
	}
	static float f(float c,int i){
	
		if(map.containsKey(c))
			return map.get(c);
		if(i == n-1){
			map.put(c,c < arr[i]? 0:arr[i]);
			return map.get(c);
		}
		if(c < arr[i]){
			map.put(c, f(c,i+1));
			return map.get(c);
		}
		map.put(c,Math.max(f(c,i+1),f(c-arr[i],i+1)+arr[i]));
		return map.get(c);
	}
}

	

/**************************************************************
	Problem: 1025
	User: coder
	Language: Java
	Result: Accepted
	Time:430 ms
	Memory:22608 kb
****************************************************************/


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3