脚本宝典收集整理的这篇文章主要介绍了01背包(容量为浮点数),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
http://acm.hdu.edu.cn/showPRoblem.PHP?pid=1864
Time LimIT: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
total Submission(s): 36208 Accepted Submission(s): 11135
//#include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdio.h> #include <queue> #include <stack> #include <map> #include <set> #include <string.h> #include <vector> #define ME(x,y) memset(x,y,sizeof(x)) #define SF(n) scanf("%d",&n) #define rep(i,n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) using namespace std; typedef long long ll ; int dp[3000009],w[30]; int main() { double n ; double v ; while(~scanf("%lf%lf",&v,&n) && n) { int flag ; memset(w,0,sizeof(w)); memset(dp,sizeof(dp)); for(int i = 1 ; i <= n ; i++) { int num ; scanf("%d",&num); flag = 1 ; int x,z ; x = y = z = 0 ; for(int j = 1 ; j <= num ; j++) { double val ; char c,d; cin >> c >> d >> val ; val = val * 100 ; if(c == ‘A‘ && x + val <= 60000) { x += val ; } else if(c == ‘B‘ && y + val <= 60000) { y += val ; } else if(c == ‘C‘ && z + val <= 60000) { z += val ; } else { flag = 0 ; } } if(x + y + z <= 100000 && flag) w[i] = x + y + z ; } int vv = v * 100 ; for(int i = 1 ; i <= n ; i++) { for(int j = vv ; j >= w[i] ; j--) { dp[j] = max(dp[j],dp[j-w[i]]+w[i]); } } printf("%.2lf\n",(double)dp[vv]/100); } return 0; }
以上是脚本宝典为你收集整理的01背包(容量为浮点数)全部内容,希望文章能够帮你解决01背包(容量为浮点数)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。