测试输入包含若干测试用例。每个测试用例的第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
#include<iostream> (720)#include<vector> #include<cmath> (808)#include<string> #include<iomanip> using namespace std; double max_c=0; //记录最大报销额 void DFS(vector<double> items,int n,double sum,double maxs) //数据,开始搜索位置,当前可报销额度,上限 { for (int i = n; i < items.size(); i++) { if (sum + items[i] <= maxs) { max_c = max(max_c, sum+items[i]); DFS(items, i + 1, sum + items[i], maxs); } } } int main() //DFS { double money; int count; while (cin >> money >> count) { if (count == 0) break; vector<double> items; //数据 for (int i = 0; i < count; i++) { int counts; double sum = 0; cin >> counts; int flag = 0; for (int i = 0; i < counts; i++) { string s; cin >> s; char a = s[0]; if (a == 'A' || a == 'B' || a == 'C') { double b = atof(s.erase(0, 2).c_str()); if (b > 600) //大于600,不录 { flag = 1; } else sum += b; } else flag = 1; //含有其他物品,不录 } if (flag==0&&sum <= 1000&&sum!=0) items.push_back(sum);//大于1000,不录 } max_c = 0; DFS(items,0,0,money); cout <<fixed<<setprecision(2)<< max_c << endl; //输出可用最大额度 } }
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; double quota,ans=0; vector<double> receipt;//存放每张有效发票的金额 void DFS(int index,double sum){ ans = max(ans,sum); if(index>=receipt.size()) return; if(sum+receipt[index]<=quota) DFS(index+1,sum+receipt[index]); DFS(index+1,sum); } int main(){ while(scanf("%lf%d","a,&n)!=EOF && n!=0){ receipt.clear();//初始化 ans = 0; for(int i=0;i<n;i++){//输入每张发票的票面金额 int num;//num是发票项数,sum是这张发票总金额 double sum=0; bool flag = true;//判断这张发票是否合法; scanf("%d",&num); getchar(); for(int j=0;j<num;j++){//输入每张发票的每项金额 double amount; char type; scanf("%c:%lf%*c",&type,&amount); if(amount<=600 && type-'A'<=2) sum += amount; else flag = false; } if(sum<=1000 && flag && sum<=quota) receipt.push_back(sum); } DFS(0,0); printf("%.2f\n",ans); } return 0; }
#include <stdio.h> #include <string.h> struct Info1 { double hash[300]; double tot; int flag; }; struct Info1 fapiao[35]; double maxi=-1; double Q; void DFS(int i,double sum,int n) { if(i==n) { if(sum>maxi) { maxi=sum; } return; } DFS(i+1,sum,n); if(sum+fapiao[i].tot<=Q&&fapiao[i].flag==1) { DFS(i+1,sum+fapiao[i].tot,n); } } int main() { int N; int i,j; char str[50]; char ch; while(scanf("%lf %d",&Q,&N)!=EOF&&N) { int m; for(i=0;i<N;i++) { fapiao[i].flag=1; fapiao[i].tot=0; memset(fapiao[i].hash,0,sizeof(fapiao[i].hash)); scanf("%d",&m); for(j=0;j<m;j++) { scanf("%s",str); double temp; sscanf(str,"%c:%lf",&ch,&temp); fapiao[i].hash[ch]+=temp; fapiao[i].tot+=temp; if(fapiao[i].hash[ch]>600) fapiao[i].flag=0; if(ch!='A'&&ch!='B'&&ch!='C') { fapiao[i].flag=0; } } if((int)fapiao[i].tot>1000) fapiao[i].flag=0; } DFS(0,0,N); printf("%.2f\n",maxi); } return 0; }这里我提供一种新的思路,也就是采用DFS来解决。可以对N个符合要求的发票进行搜索,分为选或者不选,此时0-1背包问题就转化成为了搜索问题。
package com.speical.first;
import java.util.Scanner;
/**
* 带有约束的0 1背包问题
*
* 思路: dp[j] = Math.max(dp[j], dp[j - prices[i]] + prices[i]);
*
* 注意此题的背包大小为double型,所以我们可以乘以10的次方来消除小数点
* 转换为我们熟知的int型的背包
*
* 同时对于不合法的发票(对应不合法的物体)我们把此物体的体积设置为背包的最大体积加1
* 这样当考虑该物体时,肯定不会考虑这个物体(发票)
* @author special
* @date 2018年1月7日 下午2:17:26
*/
public class Pro132 {
public static int getMaxPrice(int[] prices, int n, int maxPrice){
int[] dp = new int[maxPrice + 1];
for(int i = 1; i <= n; i++){
for(int j = maxPrice; j >= prices[i]; j--){
dp[j] = Math.max(dp[j], dp[j - prices[i]] + prices[i]);
}
}
return dp[maxPrice];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
while(input.hasNext()){
double q = input.nextDouble();
int n = input.nextInt(), count;
if(n == 0) break;
int maxPrice = (int)(q * 100);
int[] prices = new int[n + 1];
double A, B, C, price;
boolean isValid = true;
for(int i = 1; i <= n; i++){
count = input.nextInt();
A = B = C = 0;
isValid = true;
while(count-- > 0){
String data = input.next();
String[] dataArray = data.split(":");
price = Double.parseDouble(dataArray[1]);
if(dataArray[0].equals("A")){
A += price;
}else if(dataArray[0].equals("B")){
B += price;
}else if(dataArray[0].equals("C")){
C += price;
}else{ // 非 A B C 就是不合法
isValid = false;
}
}
double total = A + B + C;
if(!isValid || A > 600 || B > 600 || C > 600 || total > 1000){
prices[i] = maxPrice + 1;
}else{
prices[i] = (int)(total * 100);
}
}
System.out.format("%.2f\n", getMaxPrice(prices, n, maxPrice) / 100.0);
}
}
}
#include <cstdio> #include <iostream> #include <vector> using namespace std; float dfs(float total,vector<float> receipt){ float maxf=0; for(int i=0;i<receipt.size();i++){ if(total>=receipt[i]){ vector<float> receipt2=receipt; //因为要取第i个,所以为了让接下来的dfs不再取它,所以要设置一个比较大的值 receipt2[i]=1e9; //取第i个进行报销,加上剩下支票的可报销最大值 maxf=max(maxf,receipt[i]+dfs(total-receipt[i],receipt2)); } } //maxf是报销的最大值 return maxf; } int main() { float total;int n;vector<float> receipt; while(scanf("%f%d",&total,&n)!=-1){ receipt.clear(); if(n==0){ break; } for(int i=0;i<n;i++){ int m; scanf("%d",&m); //设置一个tag,判断能否报销 float totalprice=0,temp;bool tag=true;char c; for(int j=0;j<m;j++){ scanf(" %c:%f",&c,&temp); totalprice+=temp; if(c!='A'&&c!='B'&&c!='C'||temp>600){ tag=false; } } //可以报销的push到数组 if(tag&&totalprice<=1000){ receipt.push_back(totalprice); } } //到这里呢,就有了额度total,和需要报销的数组receipt,这两个作为参数传到dfs函数 printf("%.2f\n",dfs(total,receipt)); } } // 64 位输出请用 printf("%lld")
def cost_by_idx(invoice_list, max_cost, base_idx): res = 0.0 for i in range(base_idx, len(invoice_list)): if res + invoice_list[i] <= max_cost: res += invoice_list[i] return res while True: try: in_list = input().split() max_cost = float(in_list[0]) invoice_num = int(in_list[-1]) # 发票数 == 0,结束程序 if invoice_num == 0: break invoice_list = [] # 保存各发票可以报销的额度 for i in range(invoice_num): invoice_data = input().split()[1:] allowed_costs = [] for item in invoice_data: cate, cost = item.split(':') # 如果此发票包含不可报销类型,则跳过此发票 if cate not in ['A', 'B', 'C']&nbs***bsp;float(cost) > 600: break allowed_costs.append(float(cost)) else: # 添加单张发票可以报销的总额 if sum(allowed_costs) <= 1000: invoice_list.append(sum(allowed_costs)) invoice_list.sort(reverse=True) res = 0.0 for i in range(len(invoice_list)): res = max(res, cost_by_idx(invoice_list, max_cost, i)) print('{:.2f}'.format(res)) except Exception: break
#include<iostream> #include<iomanip> #include<string> #include<vector> #include<algorithm> using namespace std; struct fapiao { bool tag=true;//默认可以用 double A=0,B=0,C=0; int num; double sum; }; double string2double(string &S) { int len=S.size()-3; double a=0,b=0; for(int i=2;i<len;i++) a=a*10+S[i]-'0'; b=(S[len+1]-'0')*0.1+(S[len+2]-'0')*0.01; return a+b; } bool cmp(fapiao a,fapiao b) { return a.sum>b.sum; } int main() { double Q,N; while(cin>>Q>>N) { if(N==0) break; vector<fapiao> fas(N); for(int i=0;i<N;i++) {//i表示发票 int num; string S; cin>>num; fas[i].num=num; for(int j=0;j<num;j++) {//j表示发票内的款项 cin>>S; if(S[0]!='A'&&S[0]!='B'&&S[0]!='C') { fas[i].tag=false; }else if(S[0]=='A') { fas[i].A+=string2double(S); }else if(S[0]=='B') { fas[i].B+=string2double(S); }else if(S[0]=='C') { fas[i].C+=string2double(S); } } fas[i].sum=fas[i].A+fas[i].B+fas[i].C; if(fas[i].sum>1000||fas[i].A>600||fas[i].B>600||fas[i].C>600) { fas[i].tag=0; } }//将每一张发票存储好了 sort(fas.begin(),fas.end(),cmp); double max=0;//max是最大的那次贪心 double sum=0;//每一次贪心得到的由sum来存储 for(int j=0;j<fas.size();j++) {//多次贪心 sum=0; for(int i=j;i<fas.size();i++) { if(sum+fas[i].sum<=Q&&fas[i].tag==true) { sum+=fas[i].sum; } } if(sum>max) max=sum; } cout<<fixed<<setprecision(2)<<max<<endl; } }
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> using namespace std; int main(){ int n; double q; vector<double> v; while(scanf("%lf %d", &q, &n) != EOF){ if(n == 0) break; for(int i = 0; i < n; i++){ int num; scanf("%d", &num); double sum = 0; bool flag = true; for(int j = 0; j < num; j++){ char type; double price; getchar(); scanf("%c:%lf", &type, &price); if((type != 'A' && type != 'B' && type != 'C') || price > 600) flag = false; sum += price; } if(flag && sum <= q){ v.push_back(sum); } } sort(v.begin(), v.end()); double maxsum = 0; for(int i = 0; i < v.size(); i++){ double sum = v[i]; for(int j = i + 1; j < v.size(); j++){ if(sum + v[j] <= q) sum += v[j]; else break; } maxsum = max(maxsum, sum); } printf("%.2f\n", maxsum); } return 0; }
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int book[31]; double data[31]; double max_money; void DFS(double sum,double Q,int t) { if(sum > Q) return; if(sum <= Q) { max_money = max(max_money,sum); } for(int i = 0;i < t;i++) { if(!book[i]) { book[i] = 1; DFS(sum + data[i],Q,t); book[i] = 0; } } } int main() { double Q,price; int N,m; char type; while(cin >> Q >> N && N) { int t = 0; while(N--) { cin >> m; double v_total = 0,v_a = 0,v_b = 0,v_c = 0; bool flag = true; while(m--) { scanf(" %c:%lf",&type,&price); if(type == 'A') { v_a += price; } else if(type == 'B') { v_b += price; } else if(type == 'C') { v_c += price; } else { flag = false; } v_total += price; if(v_a > 600 || v_b > 600 || v_c > 600) flag = false; if(v_total > Q || v_total > 1000) flag = false; } if(m == -1 && flag) data[t++] = v_total; } max_money = 0; DFS(0,Q,t); printf("%.2lf\n",max_money); } return 0; }
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int dp[3003000]={0}; void init(){ for(int i=0;i<=3000000;i++) dp[i]=0; } int main(){ double s; int n; while(cin>>s>>n&&n){ init(); int m; int num=1; double g[100]={0}; for(int i=1;i<=n;i++){ int book=1; double h[3]={0}; cin>>m; string p; for(int j=1;j<=m;j++){ cin>>p; char k=p[0]; if(k!='A'&&k!='B'&&k!='C') book=0; else{ double ans=0; int mr; for(int l=2;l<p.size();l++){ if(p[l]=='.'){ mr=l; break; } ans*=10; ans+=p[l]-'0'; } ans+=0.1*(p[mr+1]-'0'); ans+=0.01*(p[mr+2]-'0'); h[p[0]-'A']+=ans; } } for(int j=0;j<3;j++){ if(h[j]>600){ book=0; break; } } double judge=0; for(int j=0;j<3;j++){ judge+=h[j]; if(judge>1000){ book=0; break; } } if(judge>1000) book=0; if(book==1){ for(int j=0;j<3;j++) g[num]+=h[j]; num++; } } int v[50]={0}; int w[50]={0}; for(int i=1;i<num;i++){ int o=g[i]*100; v[i]=o; w[i]=o; } int zong=s*100; for(int i=1;i<num;i++){ for(int j=zong;j>=v[i];j--){ dp[j]=max(dp[j-v[i]]+w[i],dp[j]); } } double gg=double(dp[zong])/double(100); printf("%.2lf\n",gg); } return 0; }01背包,就是开的数组有点大,必须放在主函数外边,当作全局变量
#include <stdio.h> float max,ans; void dfs(float *money,float total,int p,int *set) { ans=ans>total?ans:total; for(int i=0;i<p;i++) { if(set[i]==1 || total+money[i]>max)continue; //不符合条件,不能递归 set[i]=1; dfs(money,total+money[i],p,set); set[i]=0; } } int main() { int n; while(~scanf("%f%d",&max,&n) && n!=0) { float money[n]; //用money数组存储符合条件的*** int p=0; //指示money数组的大小 int set[n]; //在后面的dfs函数中指示是否已经算入总金额 while(n--) { int m,flag=1; //若flag为0,则***不符合条件 scanf("%d",&m); //m是***上所开物品的件数 char space,type,symbol; //space总是能捕捉到空格,type捕捉到物品类型,symbol则是冒号 float temp,sum=0; while(m--) { scanf("%c%c%c%f",&space,&type,&symbol,&temp); if(type!='A' && type!='B' && type!='C')flag=0; if(temp>600)flag=0; if(flag)sum+=temp; if(sum>max)flag=0; } if(flag)money[p++]=sum; //将符合条件的***金额存储起来 } for(int i=0;i<p;i++)set[i]=0; ans=0; dfs(money,0,p,set); printf("%.2f\n",ans); } }
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; const int maxn=35; double MAX; double DFS(double q,int index,double sum,vector<double> &t) { if(sum>q) return 0; if(index==t.size()) return sum; double a=DFS(q,index+1,sum+t[index],t); double b=DFS(q,index+1,sum,t); return max(a,b); } int main() { int n,m; double q; string s="ABC"; while(scanf("%lf%d",&q,&n)!=EOF&&n) { vector<double> t; for(int i=0;i<n;++i) { int flag=1; double sump=0; cin>>m; for(int j=0;j<m;++j) { char type; double p; scanf(" %c:%lf",&type,&p); if(s.find(type)==string::npos||p>600) flag=0; else sump+=p; } if(flag&&sump<=1000) t.push_back(sump); } printf("%.2f\n",DFS(q,0,0,t)); } return 0; }
#include<bits/stdc++.h> using namespace std; //发票上的每一项 typedef struct item{ char type; //类型 double price; //额度 }item; int n; int index_; //index_记录有效发票的数目 double a[30]; //用于存储符合要求的发票的面额 double limit,maxValue; //给定的报销额 所求蕞大报销额 double sum; double money; vector<item>v; //每个用例的每一行输入的发票 //判断该张发票是否符合要求 int judge(int n) { for(int i=0;i<n;i++) { if(v[i].type<'A'||v[i].type>'C') return 0; if(v[i].price>600) return 0; sum+=v[i].price; } if(sum>1000||sum>limit) return 0; return 1; } //背包问题 递归找出蕞大报销额度 void find(int i) { if(i==index_) //边界条件 { if(money>maxValue) maxValue = money; return; } if(money + a[i] <= limit) { money = money + a[i]; find(i + 1); money = money - a[i]; //回溯 } find(i + 1); } int main() { char s[15]; int num; int i,j; while(cin>>limit>>n&&n!=0) { memset(a,0,sizeof(a)); v.clear(); index_ = 0; maxValue = 0; money = 0; for(i=0;i<n;i++) { sum = 0; cin>>num; for(j=0;j<num;j++) { scanf("%s",s); item t; //利用sscanf 从字符串读入 sscanf(s,"%c:%lf",&t.type,&t.price); v.push_back(t); } if(judge(num)) { a[index_++]=sum; } v.clear(); } find(0); cout<<fixed<<setprecision(2)<<maxValue<<endl; } return 0; }
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100030100+5;//30张1000元的发票(扩大100倍)
int max_val; //可报销总额
int dp[maxn];
int cnt; //合法发票数
int val[maxn];//每张合法发票的额度
int main()
{
double v;
int n;
while(scanf("%lf%d",&v,&n)==2 && n)
{
cnt=0;
max_val=(int)(v*100);
for(int i=1;i<=n;i++)
{
int num;
char type;//商品类型
double va=0,vb=0,vc=0;
scanf("%d",&num);
bool flag=true;//合法发票
while(num--)
{
scanf(" %c:%lf",&type,&v);
if(type=='A') va+=v;
else if(type=='B') vb+=v;
else if(type=='C') vc+=v;
else flag=false;//含有其他种类商品
}
if(flag && va<=600 && vb<=600 && vc<=600 && va+vb+vc<=1000)
val[++cnt]=(int)((va+vb+vc)*100);
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=cnt;i++)
for(int j=max_val;j>=val[i];j--)
dp[j] = max(dp[j],dp[j-val[i]]+val[i]);
printf("%.2lf\n",(dp[max_val])/100.0 );
}
return 0;
}
#include <iostream> #include <cstdio> #include <vector> using namespace std; vector<float> validCheck; float Q, curMoney, maxMoney; int N, validCheckNum; void FindMaxMoney(int index) { if (index == validCheckNum) { if (curMoney > maxMoney) maxMoney = curMoney; return; } if (curMoney + validCheck[index] <= Q) { curMoney += validCheck[index]; FindMaxMoney(index + 1); curMoney -= validCheck[index]; } FindMaxMoney(index + 1); } int main(void) { while (cin >> Q >> N && N != 0) { vector<float>().swap(validCheck); for (int i = 0; i < N; i++) { int itemNum, valid = 1; float money, sum = 0; char checkType; cin >> itemNum; for (int j = 0; j < itemNum; j++) { scanf(" %c:%f", &checkType, &money); if ((checkType == 'A' || checkType == 'B' || checkType == 'C') && money <= 600) sum += money; else valid = 0; } if (valid == 1 && sum <= 1000) validCheck.push_back(sum); } validCheckNum = validCheck.size(); maxMoney = 0, curMoney = 0; FindMaxMoney(0); printf("%.2f\n", maxMoney); } return 0; }
}