- 浏览: 307467 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
http://poj.org/problem?id=3260
以下是从网上拷过来的分析:
题意:John去买东西,东西的价格是T(1 <= T <= 10000),John所在的地方有n(1 <= n <= 100)种的硬币,面值分别为V1, V2, ..., Vn (1 <= Vi <= 120)。John带了C1枚面值为V1的硬币,C2枚面值为V2的硬币,...,Cn枚面值为Vn的硬币(0 <= Ci <= 10000)。售货员那里每种硬币都有无限多个。问为了支付这个T,John给售货员的硬币数目加上售货员找回的零钱的硬币数目最少是多少。如果无法支付 T,输出-1
解法:支付时硬币数量有限制,为多重背包问题,通过二进制方法转化为01背包求解。找零时,硬币数量无限制,为完全背包问题。对两问题分别求解,然后找出差额为T时,两者和的最小值即为所示。
分析:
1.给钱时,硬币数有限制,为多重背包问题
2.找钱时,硬币数无限制,为完全背包问题
3.给钱上界为:T+maxValue^2,其中maxValue为最大硬币面值
证明:反证法。假设存在一种支付方案,John给的钱超过T+maxValue^2
则售货员找零超过maxValue^2,则找的硬币数目超过maxValue个
将其看作一数列,求前n项和sum(n)
根据鸽巢原理,至少有两个对maxValue求模的值相等
假设为sum(i)和sum(j),i<j
则i+1j的硬币面值和为maxValue的倍数
同理,John给的钱中也有一定数量的硬币面值和为maxValue的倍数
则这两堆硬币可用数量更少的maxValue面值硬币代替,产生更优方案
我的代码【背包九讲的风格】:
以下是从网上拷过来的分析:
题意:John去买东西,东西的价格是T(1 <= T <= 10000),John所在的地方有n(1 <= n <= 100)种的硬币,面值分别为V1, V2, ..., Vn (1 <= Vi <= 120)。John带了C1枚面值为V1的硬币,C2枚面值为V2的硬币,...,Cn枚面值为Vn的硬币(0 <= Ci <= 10000)。售货员那里每种硬币都有无限多个。问为了支付这个T,John给售货员的硬币数目加上售货员找回的零钱的硬币数目最少是多少。如果无法支付 T,输出-1
解法:支付时硬币数量有限制,为多重背包问题,通过二进制方法转化为01背包求解。找零时,硬币数量无限制,为完全背包问题。对两问题分别求解,然后找出差额为T时,两者和的最小值即为所示。
分析:
1.给钱时,硬币数有限制,为多重背包问题
2.找钱时,硬币数无限制,为完全背包问题
3.给钱上界为:T+maxValue^2,其中maxValue为最大硬币面值
证明:反证法。假设存在一种支付方案,John给的钱超过T+maxValue^2
则售货员找零超过maxValue^2,则找的硬币数目超过maxValue个
将其看作一数列,求前n项和sum(n)
根据鸽巢原理,至少有两个对maxValue求模的值相等
假设为sum(i)和sum(j),i<j
则i+1j的硬币面值和为maxValue的倍数
同理,John给的钱中也有一定数量的硬币面值和为maxValue的倍数
则这两堆硬币可用数量更少的maxValue面值硬币代替,产生更优方案
我的代码【背包九讲的风格】:
#include <iostream> #include <iomanip> #include <fstream> #include <sstream> #include <algorithm> #include <string> #include <set> #include <utility> #include <queue> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; #define inf 0x3fffffff //需要有两个dp,一个是付钱【多重背包】,一个是找钱【完全背包】,2者必须独立求解 int dp[25000], dp2[25000], w[105], num[105], MAX, maxs; //dp存放的值是硬币个数,dp数组的下标意义:钱的数量 //dp[j]:给j钱至少需要dp[j]个硬币,dp2[j]:找j钱至少需要dp2[j]个硬币 void _01pack (int cost, int weight) { int j; for (j = MAX; j >= cost; j--) //取最小时由于初始化为负无穷,所以要讨论,下面同理 { if (dp[j] >= 0 && dp[j-cost] >= 0) dp[j] = min (dp[j], dp[j-cost] + weight); else if (dp[j-cost] >= 0) dp[j] = dp[j-cost] + weight; } /*cout << "-" << endl; //打表调试 for (j = 0; j <= 400; j++) cout << dp[j] << ' '; cout << endl;*/ } void compack (int cost) { int j; for (j = cost; j <= MAX; j++) { if (dp[j] >= 0 && dp[j-cost] >= 0) dp[j] = min (dp[j], dp[j-cost] + 1); else if (dp[j-cost] >= 0) dp[j] = dp[j-cost] + 1; } /*cout << "--" << endl; //打表调试 for (j = 0; j <= MAX; j++) cout << dp[j] << ' '; cout << endl;*/ } void mulpack (int cost, int weight, int amount) //付钱多重背包,包含上面2个函数 { if (cost * amount >= MAX) { compack (cost); return ; } int k = 1; while (k <= amount) { _01pack (k*cost, k*weight); //注意,01背包必须得有weight变量,因为这里价值不一定是1了 amount -= k; k <<= 1; } _01pack (amount*cost, amount*weight); } void compack2 (int cost) //找钱完全背包 { int j; for (j = cost; j <= maxs; j++) { if (dp2[j] >= 0 && dp2[j-cost] >= 0) dp2[j] = min (dp2[j], dp2[j-cost] + 1); else if (dp2[j-cost] >= 0) dp2[j] = dp2[j-cost] + 1; } /*cout << "---" << endl; for (j = 0; j <= 366; j++) cout << dp2[j] << ' '; cout << endl;*/ } int main() { int n, t, i, mins, j; while (cin >> n >> t) { maxs = 0; for (i = 0; i < n; i++) { cin >> w[i]; if (maxs < w[i]) maxs = w[i]; } maxs *= maxs; //找钱上界 MAX = t + maxs; //付钱上界 for (i = 0; i < n; i++) cin >> num[i]; for (i = 1; i <= MAX; i++) dp[i] = -inf; dp[0] = 0; //dp初始化,付钱 for (i = 0; i < n; i++) mulpack (w[i], 1, num[i]); for (i = 1; i <= maxs; i++) dp2[i] = -inf; dp2[0] = 0; //dp2初始化,找钱 for (i = 0; i < n; i++) compack2 (w[i]); mins = inf; for (j = t; j <= MAX; j++) //枚举所以付钱情况,枚举所用硬币数,找出最小 { if (dp[j] >= 0 && dp2[j-t] >= 0)//检查是否可以付j钱,是否可以找j-t钱,买东西要花t钱 mins = min (mins, dp[j]+dp2[j-t]); } if (mins == inf) //发现没有合法情况 puts ("-1"); else cout << mins << endl; } return 0; }
发表评论
-
《挑战编程》第11章-动态规划
2013-02-02 12:46 1459UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1651// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2187// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3083// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1907// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1635// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 1949// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1410// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1803// [解题方法] // 对大象增加编号属性i,以免 ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1366KIDx的解题报告 题目链接:http://acm ... -
【DP最大公共子序列】HDU 1159/1080/1503
2012-03-11 18:04 3110KIDx的解题报告 第一题(比较简单,不详细解): ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3557KIDx的解题报告 题目链接:http://acm.h ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1439KIDx 的解题报告 题目链接:http://codeforc ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1356KIDx 的解题报告 http://codeforces.c ... -
【最长递增子序列O(nlgn)算法】HDU 1025
2011-09-10 15:36 1549http://acm.hdu.edu.cn/showprobl ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2537KIDx 的解题报告 http://acm.hdu.ed ... -
【二维分组背包记录路径】暗黑破坏神
2011-08-24 19:48 1986http://openoj.awaysoft.com/Judg ... -
HDU 1087 Super Jumping! Jumping! Jumping!
2011-06-02 18:59 3241http://acm.hdu.edu.cn/showprobl ... -
POJ_3211_Washing Clothes
2011-05-13 23:05 1538http://poj.org/problem?id=3211 ... -
POJ_1742_Coins
2011-05-13 22:33 984http://poj.org/problem?id=1742 ...
相关推荐
poj 3260 The Fewest Coins.md
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
O(nlogn)凸包问题 poj2187
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
poj 3310 的代码和方法说明,个人原创
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...