博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
DP-01背包 (题)
阅读量:6230 次
发布时间:2019-06-21

本文共 3804 字,大约阅读时间需要 12 分钟。

 nyoj 325   http://acm.nyist.net/JudgeOnline/problem.php?pid=325         

        zb的生日

时间限制:
3000 ms  |  内存限制:65535 KB
难度:
2
描述
今天是阴历七月初五,acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日,经过调查,zb发现C小加和never都很喜欢吃西瓜,而且一吃就是一堆的那种,zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候,遇到了一个难题,never和C小加不在一块住,只能把西瓜分成两堆给他们,为了对每个人都公平,他想让两堆的重量之差最小。每个西瓜的重量已知,你能帮帮他么?
输入
多组测试数据(<=1500)。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数,W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量
输出
输出分成两堆后的质量差
样例输入
55 8 13 27 14
样例输出     3
题目分析 :
  题目所求 , 将一堆西瓜分成两堆 , 最小的差值是多少 , 那肯定就会想到 , 我平均分开的两堆西瓜 ,他们分别的重量一定是 最接近总和的一半 , 所以我可以求出总和的一半 , 然后 就转化为在总和的一半中 我向里面放东西 , 最多可以放多少 , 即转化为 01背包  。    这个思路是没问题的 , 但按照正常的方法敲 , 则会超时 , 原因在哪呢 ? 通过我搜题解 发现 问题就在于我用了 C++ 系统给的函数 max  , 如果我不用 max , 改用 if  判断的话 , 此题会险过 , 差几十毫秒 , 但后来我有试了下 , 自己写一个 Max 函数 , 则会快 500 多毫秒 。   
附上代码 :
#include 
#include
#include
#include
using namespace std ;#define Max(a,b) a>b?a:bint dp[100020] ;int weight[25] ;int main ( ) { int n , i , j ; while ( ~scanf ( "%d" , &n ) ) { memset ( dp , 0 , sizeof(dp) ) ; int sum = 0 ; for ( i = 1 ; i <= n ; i++ ) { scanf ( "%d" , &weight[i] ) ; sum += weight[i] ; } int k = sum / 2 ; for ( i = 1 ; i <= n ; i++ ) { for ( j = k ; j >= weight[i] ; j-- ) { dp[j] = Max ( dp[j] , dp[j-weight[i]] + weight[i] ) ; // if ( dp[j-weight[i]] + weight[i] > dp[j] ) // dp[j] = dp[j-weight[i]] + weight[i] ; } } printf ( "%d\n" , sum - 2 * dp[k] ) ; } return 0 ;}

 

 

 

Problem Description
现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书(A类)、文具(B类)、差旅(C类),要求每张发票的总额不得超过1000元,每张发票上,单项物品的价值不得超过600元。现请你编写程序,在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
 

 

Input
测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N,其中 Q 是给定的报销额度,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

 

分析

  题目所求 , 在所有的数据中 , 寻求最大报销额 , 对于每组数组 , 我有选或不选的权利 , 即转化为 01背包问题 。

  但是要注意的一点是 , 题目中的金额是小数 , 需要将其扩大100倍 , 转化为整数  。

 

代码示例 :

  

#include 
#include
#include
#include
using namespace std ;#define Max(a,b) a>b?a:bint dp[3000020] ;int money[1005] ;int main ( ) { double s , x ; int n , m ,sign , ss , sum ; char ch ; while ( cin >> s >> n && n ) { int k = 1 ; ss = (int)( s * 100 ) ; memset ( dp , 0 , sizeof(dp) ) ; while ( n-- ) { scanf ( "%d" , &m ) ; getchar ( ) ; sum = 0 , sign = 1 ; while ( m-- ) { scanf ( " %c:%lf" , &ch , &x ) ; int mm = ( int ) ( x*100 ) ; sum += mm ; if ( mm > 60000 || sum > 100000 ) sign = 0 ; if ( ch != 'A' && ch != 'B' && ch != 'C' ) sign = 0 ; // printf ( " mm = %d sum = %d sign = %d \n" , mm , sum , sign ) ; } if ( sign ) money[k++] = sum ; } // printf ( " ss = %d sum = %d " , ss , sum ) ; // for ( int i = 1 ; i < k ; i++ ) cout << money[i] << '\t' ; for ( int i = 1 ; i < k ; i++ ) { for ( int j = ss ; j >= money[i] ; j-- ) { dp[j] = Max ( dp[j] , dp[j-money[i]]+money[i] ) ; // cout << dp[j] ; } // cout << '\n' ; } printf ( "%.2f\n" , dp[ss] / 100.0 ) ; } return 0 ;}

 

转载于:https://www.cnblogs.com/ccut-ry/p/7352503.html

你可能感兴趣的文章
探讨SQL Server并发处理存在就更新七种解决方案
查看>>
当今游戏大作share的特性大盘点
查看>>
CountDownLatch使用
查看>>
创建 Image - 每天5分钟玩转 OpenStack(21)
查看>>
sql server中根据地图经纬度算距离
查看>>
VMware“该虚拟机似乎正在使用中”问题
查看>>
在Asp.Net中操作PDF – iTextSharp - 使用表格
查看>>
在一个文件中有10G个整数,乱序排列,要求找出中位数
查看>>
数据刷新中的并行改进(三)
查看>>
出去吃顿饭容易嘛(r11笔记第5天)
查看>>
IMP-00009: 导出文件异常结束
查看>>
Java AIO 入门实例(转)
查看>>
SSAS中CUBE行权限数据级权限控制
查看>>
HDOJ(HDU) 2186 悼念512汶川大地震遇难同胞——一定要记住我爱你
查看>>
git 专题
查看>>
c#中const与readonly区别
查看>>
JavaScript---网络编程(11)--DHTML技术演示(4)-单选框/下拉菜单/添加文件
查看>>
解决WebView调用loadData()方法显示乱码的问题
查看>>
ThinkPHP Where 条件中使用表达式
查看>>
WPF 引用DLL纯图像资源包类库中的图片
查看>>