POJ 1252 Euro Efficiency ( 完全背包变形 && 物品重量为负 )
2024-10-07 09:38:06
题意 : 给出 6 枚硬币的面值,然后要求求出对于 1~100 要用所给硬币凑出这 100 个面值且要求所用的硬币数都是最少的,问你最后使用硬币的平均个数以及对于单个面值所用硬币的最大数。
分析 :
问题建模就是属于完全背包了,但是和普通的完全背包不一样,这题可以使用硬币的负数值,其实面对负数面值的情况,解决方法将更新数序和普通完全背包的更新顺序相反即可,然后正反更新两次就能得出最后的答案了。在普通物品重量只有正数的情况下对于一个 dp[i] 是从下标值小于 i 的状态转移而来,为了达到物品能够无限取这一条件 ( 可以参考《挑战程序设计竞赛》里面对于完全背包递推式子的解释 ) ,而负数重量的时候 dp[i] 是从下标值大于 i 的状态转移而来,故更新方向需和正数重量相反,其实这么说也是很抽象的,建议还是先去看看《挑战》里面对于完全背包原来的分析可能比较好理解。然后有一点值得注意的就是如果 dp 数组下标的更新需要开到起码 1400 ==> 考虑 1、96、97、98、99、100 这一个例子,如果要凑成 ( 1 + 96 ) / 2 的话大概需要 25个左右 也就是需要使用大概需要25/2=13个面值为 100 的硬币,价值能达到 1300.....
import java.io.*; import java.lang.reflect.Array; import java.util.*; import java.math.*; import java.util.Arrays; public class Main { public static void main(String[] args){ Scanner cin = new Scanner (new BufferedInputStream(System.in)); int[] dp = new int[2333]; int[] arr1 = new int[6]; int[] arr2 = new int[6]; int nCase; final int num = 6; nCase = cin.nextInt(); for(int Case=1; Case<=nCase; Case++){ for(int i=0; i<num; i++) arr1[i] = cin.nextInt(); for(int i=0; i<num; i++) arr2[i] = -arr1[i]; for(int i=0; i<2333; i++) dp[i] = 1000000; dp[0] = 0; for(int i=0; i<num; i++) for(int j=arr1[i]; j<=2000; j++) dp[j] = Math.min(dp[j], dp[j-arr1[i]] + 1); for(int i=0; i<num; i++) for(int j=2000-arr2[i]; j>=0; j--) dp[j] = Math.min(dp[j], dp[j-arr2[i]] + 1); int MaxNUM = 0; double Sum = 0; for(int i=0; i<=100; i++){ MaxNUM = Math.max(dp[i], MaxNUM); Sum += (double)dp[i]; } System.out.printf("%.2f %d\n", Sum/100.0, MaxNUM); } } }
最新文章
- js获取给定月份的N个月后的日期
- WCF初探-10:WCF客户端调用服务
- unity, 查看.anim中的动画曲线(和帧)
- 关于Eclipse插件开发-----加入首选项(preferencePages)
- VellCar(barracuda buggy)
- Wide character in print at a2.pl line 返回json 需要encode_utf8
- c#基础-----数据类型,转义字符,引用类型,类型转换
- iOS 参考 网络书籍
- [51nod1457]小K vs. 竹子
- URI ,URL 和 URN
- c++ switch和case的用法
- ORACLE 当字段中有数据如何修改字段类型
- 1093 字符串A+B
- [转载]Linux下终端字体颜色设置方法
- 为什么说Java语言是平台无关的?
- 伯克利、OpenAI等提出基于模型的元策略优化强化学习
- Android逆向-java代码基础
- iOS多线程与网络开发之NSOperation
- npm使用过程中的一些错误解决办法及npm常用命令和技巧
- day 2 函数的嵌套