`

POJ_3260_The Fewest Coins

阅读更多
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面值硬币代替,产生更优方案


我的代码【背包九讲的风格】:

#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;
}
2
1
分享到:
评论

相关推荐

    poj 3260 The Fewest Coins.md

    poj 3260 The Fewest Coins.md

    poj_1699.rar_1699_poj_poj1699

    【标题】"poj_1699.rar_1699_poj_poj1699" 提供的是一个关于POJ(编程在线判题系统)第1699题的解决方案,其中包含了该问题的代码实现和解题思路。POJ是一个流行的在线编程竞赛平台,它为参赛者提供了各种算法题目,...

    poj2775.rar_poj_poj 27_poj27_poj2775

    标签"poj poj_27 poj27 poj2775"进一步确认了这是一道关于POJ平台的编程挑战,其中"poj_27"可能是表示第27类问题或者某种分类,而"poj27"可能是对"poj2775"的简写。 压缩文件中的"www.pudn.com.txt"可能是一个链接...

    poj_2682(3).rar_C++ 数组扩充_poj 26_poj 2682_poj26

    标题中的"poj_2682(3).rar"是一个指向编程竞赛问题的引用,通常这类问题在网站如POJ(Programming Online Judge)上出现,供程序员解决并提交代码进行测试。这个问题的编号是2682,可能涉及到特定的数据结构或算法...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    Poj_1102_.rar_poj11

    标题"Poj_1102_.rar_poj11"暗示了这是一个关于解决Poj_1102问题的资源包,通常在编程竞赛或在线判题系统如POJ(Problem Set of Judge Online)上遇到。POJ是中国的一个在线编程训练平台,提供了各种算法题目供用户...

    poj_3613解题报告

    2遍dp poj_3613解题报告 poj_3613解题报告

    poj_3310.rar_3310_poj

    【标题】"poj_3310.rar_3310_poj"是一个与编程竞赛相关的压缩包,其中包含了对POJ(Problem Online Judge)3310问题的解决方案和详细解析。POJ是一个著名的在线编程竞赛平台,提供各种算法题目供参赛者练习和提交...

    ACM.zip_ACM_poj_poj3187_poj3669

    标题 "ACM.zip_ACM_poj_poj3187_poj3669" 提供的信息表明,这个压缩包包含的是与ACM(国际大学生程序设计竞赛)相关的编程题目解决方案,具体是POJ(Programming Online Judge)平台上的两道题目,编号分别为poj3187...

    1010_stamps.zip_1010_POJ 1010_poj_poj stamps_poj10

    《POJ 1010 Stamps:解题思路与陷阱分析》 POJ 1010,也被称为“邮票问题”,是编程竞赛中的一道经典题目,旨在考察参赛者的动态规划和数学思维能力。这个题目在编程爱好者中具有较高的知名度,因为它涉及到有趣的...

    pku_poj_2187.rar_poj 2187_凸包问题

    标题中的“pku_poj_2187.rar_poj 2187_凸包问题”表明这是一个关于北京大学(Peking University, PKU)编程竞赛平台POJ上的第2187题,题目主要涉及凸包问题。描述中的“O(nlogn)凸包问题 poj2187”提示我们解决这个...

    poj_1002_487.rar_poj 1002

    【标题】"poj_1002_487.rar_poj 1002"指的是北京大学在线编程平台上的第1002道题目,这道题目涉及到计算机科学中的算法设计与实现,特别是字符串处理和哈希映射。在这个问题中,我们需要编写一个程序,该程序能够...

    POJ3277.rar_3277 poj_poj3277_多个面积_线段树

    标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...

    C_(POJ_1854)(分治).cpp

    C_(POJ_1854)(分治).cpp

    poj1990.rar_POJ 19_poj_poj19

    《POJ 1990:树状数组解题策略详解》 在编程竞赛的世界里,POJ(Programming Online Judge)是一个备受瞩目的在线评测系统,它提供了丰富的编程题目供参赛者挑战。其中,编号为1990的题目是一道涉及数据结构与算法...

    D_(POJ_1723)(思维)(sort).cpp

    D_(POJ_1723)(思维)(sort).cpp

    D_(POJ_1723)(思维)(第k大数).cpp

    D_(POJ_1723)(思维)(第k大数).cpp

    jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c

    标题中的"jihe.rar_2289_POJ 3714_poj3714_poj3714 Ra_visual c" 提到了一个压缩文件,可能包含有关编程竞赛或算法解决的资源,特别是与POJ(Problem On Judge)平台上的问题3714相关的。"Ra_visual c"可能指的是...

    POJ_keptsl6_C++_

    标题“POJ_keptsl6_C++_”表明这是一个关于编程竞赛(POT, Problem Set of Judges)的资源,特别关注C++语言的解决方案。这些竞赛通常涉及到算法设计和实现,以解决各种计算机科学问题。"keptsl6"可能是用户特定的标记...

    poj_cpp.zip_MS_292AC_

    【标题】"poj_cpp.zip_MS_292AC_" 提示我们这是一份与POJ(编程在线判题系统)相关的压缩包,主要包含C++语言的解答,且可能涉及了MS(Microsoft)和292AC这两个特定的关键词。在POJ平台上,"MS_292AC_"可能是某个...

Global site tag (gtag.js) - Google Analytics