首页 文章
  • 1 votes
     answers
     views

    修正硬币变换的伪多项式时间算法

    在考虑硬币改变时我想到了以下问题,但我不知道有效(伪多项式时间)算法来解决它 . 我想知道是否有任何伪多项式时间解决方案,或者可能是我遗漏的一些经典文献 . 有一个众所周知的解决硬币变化问题的方法,它要求如下: 你有个硬币,的值为. 存在多少个硬币子集,这样硬币值的总和就是? 动态编程解决方案在中运行,是经典的 . 但是我对以下几点概括感兴趣: 如果硬币不再仅具有的值,而是可以假设一组值怎么办?现...
  • 0 votes
     answers
     views

    硬币改变算法

    只想仔细检查一下这段代码不会有任何错误,主要与模数运算符有关,我不确定 . 问题是: 问题:编写一个ACL算法,给定一个项目的成本(小于或等于一美元),给出买方在递交时可获得的50美分,20美分,10美分,5美分和1美分硬币的数量超过一美元 . 您必须尽量减少更改中的硬币数量 . 我的解决方案是: Algorithm coin_change { int cost, change, fift...
  • -1 votes
     answers
     views

    如何将一笔钱兑换成纸币和硬币

    如何将一定数量的钱换成纸币和硬币?让我们说输入是1234,26,我们有1000,500,200,100,50和20,20,1和0.5的硬币的注释?因此,如果输入大于.25且小于0.75,如果它在.75和1.00之间,它应该四舍五入为1x 1,如果它小于.25,它应该四舍五入为零?¨这个确切的程序所需的输出看起来像这样: 1x: 1000 1x: 200 1x: 20 1x: 10 4x:...
  • 1 votes
     answers
     views

    硬币变换算法 - 具有一维阵列的DP

    我在这里遇到了硬币变化问题的解决方案:Coin Change . 在这里,我能够理解第一个递归方法,第二个使用DP和2D数组的方法 . 但我无法理解第三种解决方案背后的逻辑 . 据我所知,最后一种方法适用于考虑硬币变化中使用的硬币序列的问题 . 我对么?如果我错了,任何人都可以解释我 .
  • 0 votes
     answers
     views

    硬币更换功能使用无界背包python

    我正在尝试写一个硬币更换功能 . 我的想法是,我有无限的面额和任何 Value ,并试图看到我能得到什么样的改变 . 我认为这可以像一个无限的背包程序,但我得到一个奇怪的输出,我不明白这意味着什么 . 我想也许是因为我输入了值和小数,并且想要将函数中的值更改为float但是这给了我一个错误并且不会运行程序 . 有人可以解释我目前的输出说的是什么吗?是否有可能用小数做这种事情?我怎样才能改善这个? ...
  • 0 votes
     answers
     views

    算法 - java中的硬币变化

    我看到了很多硬币更换问题,这个问题非常独特 . 我尝试使用DP和递归,但我无法解决它 . 这就是问题: 让我们说给定价格,X,其中X是美分,我有5个有限硬币面额,1,5,10,20,50 . 我有不同数量的1,5,10,20,50美分硬币 . 我想用最大硬币数量来制作价格X.我该怎么做?(假设X总是可以用手头的硬币制作) 例如,如果价格X = 52和 我有3分1美分硬币 我有4美分的5美分硬币 我...
  • 2 votes
     answers
     views

    硬币改变算法C.

    我遇到了一个针对以下问题的工作算法的麻烦 . 鉴于确定的可用硬币数量分别为100,50,25和10美分,我需要找到如何将这些硬币的组合装入给定值x . (它不一定是最佳的,可用硬币的任何组合都可以) . 到目前为止,我已经有了这个代码,仅适用于某些情况 . struct coins{ int valor; int quant; }; int change = 0; int ch...
  • 0 votes
     answers
     views

    硬币改变 . 动态编程

    我在网上找到了这个算法并且它可以工作,但我不知道为什么 . 即使有一个视频解释它 . 这是代码: public int numberOfSolutionsOnSpace(int total, int arr[]){ int temp[] = new int[total+1]; temp[0] = 1; for(int i=0; i < arr.length; i+...
  • -2 votes
     answers
     views

    返回更改程序小数c

    我的编程课程的练习要求我们为收银员编写一个程序,该程序会提示应付金额和收到的金额并计算更改 . 它还必须计算所需的美元,四分之一,硬币,硬币和便士的数量 . 它工作正常,直到达到硬币,镍币和硬币 . 这就是输出变得难以接受的地方 . 我还注意到visual studio读取0.10为.1000000000000000056 . 镍币和硬币相同,但美元或季度不会发生这种情况 . 我已经尝试了几种不同...
  • 0 votes
     answers
     views

    最低硬币改变类给出了错误答案

    试图[解决] leetcode(322)中的问题: 您将获得不同面额的金币和总金额 . 编写一个函数来计算构成该数量所需的最少数量的硬币 . 如果这笔钱不能由任何硬币组合弥补,则返回-1 . 我被困在这个输入中:coins = [2]和target = 3 我想知道为什么它会返回0?我调试了这个,但无法搞清楚 . class Solution(object): def coinChan...
  • 0 votes
     answers
     views

    将低效的递归硬币变换函数转换为迭代

    我有一个低效的递归硬币更改功能,可以计算给定金额的硬币组合数量 . 如果可能的话,我想将其转换为更有效的迭代函数 . 一个问题是我使用回溯来尝试在称为面额的数组中的不同硬币 . 我也在使用memoization但是当数量很大时它不会加快速度 . 这是我的代码: unsigned long long CalculateCombinations(std::vector<double> &a...
  • -2 votes
     answers
     views

    Python功能:从购买金额中查找更改

    我正在寻找最有效的方法来计算购买金额的变化金额(季度,硬币,镍币和硬币) . 购买金额必须低于1美元,更改金额为1美元 . 我需要知道有多少人,硬币,镍币和便士才会回来 . 设置字典是最好的吗?
  • 3 votes
     answers
     views

    JavaScript - 这种硬币更改算法有什么问题

    我正在尝试使用贪心算法计算在JavaScript中达到金额所需的最小硬币数量 返回结果将是一个由每个级别的硬币数组成的数组 我决定创建一个可以解决这个问题的函数,但它不起作用 window.addEventListener('load', function(e) { function calculateChange(coins, total) { var sum = 0; va...
  • 3 votes
     answers
     views

    仅使用超过阈值的指定面额的硬币可以获得的最小金额

    换句话说,给定一组n个正整数 A 和一个阈值 B ,我想找到最小的 C ,这样: C > B C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n] , k[i] 是整数> = 0 作为示例 A = { 6, 11, 16 } 然后我们可以获得的值是: { 0, 6, 11, 12, 16, 17, 18, 22, 23, 24,...
  • 1 votes
     answers
     views

    最大限度地减少转手的硬币数量[关闭]

    你有一套硬币5¢,10¢,20¢,50¢,1 $,2 $以及每种面额数量有限的硬币 . 当您支付一定金额时,有两种可能性:您支付正确的金额或您支付的金额超过需要,并从职员收到正确的更改 . 如何最大限度地减少转手的硬币数量(即最小化你给的硬币数量加上你收到的硬币数量) . 假设金额总是支付,而职员拥有无限数量的硬币,而且他总是选择最有效的方式来回报变化 . 我认为,为了尽量减少转手的硬币数量,你必...
  • 2 votes
     answers
     views

    硬币更换问题与每个面额的无限数量的硬币

    我想知道硬币变化问题的算法的想法,其中每个面额具有infinte数量的硬币 . 意味着如何应用DP(如标准的硬币更换问题)例如在第1,10,15组中,更改为35给出 - 2个硬币10和1个硬币15 还给我一个强制算法的想法 . 我知道迭代所有集合 . 但是如何在强制执行时改变每枚硬币的数量
  • 0 votes
     answers
     views

    自下而上接近最小硬币数量的变化

    我正在构建一个自下而上的解决硬币变化问题的方法 . 我必须给出所需更改所需的最少数量的硬币 . 由于给定的面额不能形成 Value ,因此可能无法进行更改 . 例如,给定的面额是{4,8}并且他们要求更改5然后就不可能给出5.我构建了下面的程序并且它适用于大多数情况,除非不可能形成所请求的更改 . 例如,当面额仅为{4}且我请求5时,它返回一个为假的 . 我该怎么做才能解决这个问题? 这里P表示所...
  • 12 votes
     answers
     views

    SICP例子:计数变化,无法理解

    我是麻省理工学院开放式课程的SICP课程的初学者,使用视频讲座和在线提供的书籍 . 昨天我遇到了一个例子,它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量 . 这个问题有一个简单的解决方案作为递归过程: (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ...
  • 0 votes
     answers
     views

    用有限的硬币改变C#的硬币

    我构建了以下硬币更改(C#),它完美地运行: class Program { static int amount = 0; static void Main(string[] args) { EnterAmount(); int[] coins = new int[] { 500, 10...
  • 0 votes
     answers
     views

    Min-Coin改变变化

    Min-Coin Change问题已得到充分研究(可在此处找到解释:http://www.algorithmist.com/index.php/Min-Coin_Change),但我有兴趣解决它的变化: 对于一组值V,确定最小硬币组C,使得V中的每个值可以作为C中的硬币之和获得,其中该组中的每个硬币可以仅使用最多一次 . 最小的我们是指最少的硬币数量 . 例如,如果V = {3,8,9,10,...
  • 1 votes
     answers
     views

    最小硬币自上而下的解决方案没有给出预期的结果

    我们有一个实习生使用自上而下的方法解决最小硬币问题 . 问题陈述给出一组硬币,返回形成总和所需的最小硬币 . 另外返回形成总和的硬币 . Eg: coins = {7, 3, 2, 6}, total = 13, result should be minCoins = {2}, coinsUsed = {7,6} 这是代码 package dp; import java.util.ArrayL...
  • 1 votes
     answers
     views

    用于分配机器的视觉硬币改变系统

    最近我被赋予了一项工作,在一个新的项目中工作...我已经做了一些日常和夜晚的思考如何处理它....不幸的是,这个想法没有成功,目前正在设计阶段挣扎 . 基本上前提是: "The management of Ruddles, a well known local department store has decided to implement certain changes to the...
  • 0 votes
     answers
     views

    使用递归进行硬币更改的基本案例是什么?

    我基本上试图通过递归解决硬币变化问题,这是我到目前为止 - : #include<iostream> #include<conio.h> using namespace std; int a[]={1,2,5,10,20,50,100,200},count=0; //i is the array index we are working at //a[] contain...
  • 0 votes
     answers
     views

    跟踪递归硬币更改算法

    我试图跟踪这个硬币变化问题的递归算法,M = 10,c = {5,3,1}和d = 3 . M是需要改变的货币 Value ,c是可用的不同硬币值,d是可用的不同硬币值的数量 . 我很困惑如何追踪它 . RecursiveChange(M,c,d) if M = 0 return 0 bestNumCoins <- infinity for i -> 1 to d i...
  • 1 votes
     answers
     views

    迭代方法似乎比递归实现(硬币更改)慢

    The problem from uva OJ my solution with recursion #include <cstdio> using namespace std; #define garbaze 0 //number of ways changes can be made int coins[] = {garbaze,50,25,10,5,1}; //order ...
  • 1 votes
     answers
     views

    递归硬币改变c

    每次递归调用最小函数时,我的程序似乎都会崩溃 . 任何人都可以告诉我它崩溃的原因 . 在我调用最小函数后它会立即冻结 . 是因为我使用矢量吗? #include <iostream> #include <vector> #include <math.h> #include <algorithm> using namespace std; int ...
  • 0 votes
     answers
     views

    硬币改变算法JS

    我一直试图为这个算法提出一个解决方案3-4天,但似乎没有任何效果,可用的解决方案对我来说更先进 . 它必须通过条件解决,因此不需要递归或动态编程 . 鉴于以下面额,我需要确定给出变化所需的最少硬币数量:1,0.5,0.2,0.1,0.05,0.02和0.01 . 输入如下: 物品的价格 由客户支付的金额 目前的想法: let price = +gets(); let paidSum = +gets...

热门问题