硬币更换问题:自上而下的方法似乎不是多项式的

文章/答案/技术大牛

发布

1回答

python、dynamic-programming、coin-change

硬币兑换问题(参见leet代码页here)在一个数组c中给出了一些特定面额的硬币。然后，给定目标金额t，我们希望找到获得该目标金额所需的最小硬币。原则上，这与科尔门et.al的“算法导论”一书的第15.1节中描述的最优杆切割问题非常相似。根据他们的方法，我实现了硬币找零问题的自上而下和自下而上的</e

浏览 17提问于2020-12-14得票数 1

回答已采纳

1回答

改进型硬币变化的伪多项式时间算法

algorithm、dynamic-programming、coin-change

我在思考硬币变化的时候想到了下面的问题，但我不知道有一个有效的(伪多项式时间)算法来解决它。我想知道是否有任何伪多项式时间解，或可能是一些经典文献，我错过了。现在的问题是:有多少个硬币子集存在，例如存在一个硬币的赋值，以至于这些硬币的价值之和是 (经典的硬币换币问题实际上是这个问题

浏览 3提问于2017-10-25得票数 1

1回答

mellon销售农民的一种算法

algorithm、analysis、backtracking、coin-change

我在网上看到的问题:一个卖瓜的农民有n个瓜。每个甜瓜的重量，一个整数(磅)，是不同的。一位顾客要了整整一百万磅未切好的西瓜。现在，农夫有以下问题:如果有可能满足客户，他应该通过尽可能有效地找到合适的瓜来做到这一点，否则就告诉客户不可能满足他的要求。注意:这不是家庭作业，顺便说一下，我只是需要指导。我的回答是:这似乎类似于硬币兑换问题(背包)和子

浏览 0提问于2013-07-17得票数 0

回答已采纳

1回答

2次方集划分的多项式时间算法？

algorithm、complexity-theory、partition、np

这更多地是一个算法/证明问题，而不是编程/实现，所以如果StackOverflow不是适合它的地方，请原谅。假设我们有一组数字，每个数字都必须是正整数和2的幂。我们希望将集合划分为A和B，其中每个元素都必须位于精确的A或B中，这样A的元素之和等于B元素的和。将一个分区返回到A和B中，以便它们的和相等？当然，如果没有多项式时间算法

浏览 4提问于2014-12-01得票数 2

回答已采纳

3回答

子集推理NP-完全？

algorithm、np-complete

考虑以下问题：struct Fact set<int> positions}这个问题是NP完全的<

浏览 3提问于2012-05-17得票数 5

回答已采纳

3回答

面试:为n美分(任意面额)进行改变

algorithm

这个问题是面试中一个越来越困难的问题的一部分.它一开始就这么简单：从最大面额d_i开始，取它们的最大数目，使你不超过n，m_i。取n- (d_i)(m_i)，然后对下一个最大面额重复。(4)好的，你能

浏览 5提问于2014-09-15得票数 6

回答已采纳

1回答

是否存在发件人无法证明特定密文属于特定明文的加密系统？

encryption、public-key、symmetric、zero-knowledge-proofs、deniable-encryption

我在尝试创建一个信息传输系统可以验证谁是此邮件的发送方。是否有任何现有的加密协议可以完成这项工作？这个加密协议可以是交互式的/非交互式的、对称的/不对称的或任何其他的.只需要把工作做完。我对密码

浏览 0提问于2020-01-20得票数 1

回答已采纳

1回答

对一个对手来说，参加PPT意味着什么？

complexity、security-definition

我一直在阅读这个问题，其中给出了我的详细描述，我知道多项式时间对手是一个对手，唯一可行的策略是那些花费多项式时间运行的策略；无论如何，我不明白为什么我们要求对手是概率的。在Katz的书中解释说，这是自然的，因为诚实的各方必须是概率的(为了生成随机密钥等等)，实际上这对我来说并不是很自然的(诚实的当事方是概率的这一事实并不意味着我们必须考虑对手也是

浏览 0提问于2014-06-21得票数 9

回答已采纳

2回答

硬币变化的自上而下方法中的问题(类似于0-1背包问题)

python、dynamic-programming、topdown

硬币兑换，问题如下：归还最少数量的硬币，你需要弥补这个数额。如果这个数额的钱不能由任何组合的硬币，回报-1。你可以假设你有无限数量的每一种硬币。示例1：示例2：输入:硬币<

浏览 5提问于2021-04-13得票数 0

回答已采纳

2回答

每种类型只有一枚硬币时的修正换币问题

algorithm、dynamic-programming、greedy

给定一套总面额和总金额，我们必须找到准确计算总数所需的最小硬币数量。您如何比较贪婪方法和动态编程方法？编辑:示例:我有面值为1、2、3、5的现金。每个面值我只有一枚硬币。我想用最少的硬币数换成11英镑的零钱。答案是4(1+2+3+ 5)。如果我有每个面额的无限供应，答案应该是3 (5 +5+1或5+3+ 3)。

浏览 0提问于2019-11-19得票数 1

2回答

递归可以是动态规划吗？

recursion、dynamic-programming、fibonacci

我被要求使用动态规划来解决一个问题。关于什么是动态规划，我的笔记好坏参半。我认为这需要一种“自下而上”的方法，即先解决最小的问题。有一件事与我的信息相矛盾，那就是，如果同一个子问题不止一次得到解决，是否可以是动态规划，就像递归中的情况一样。 return 1 return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2) 在这种情

浏览 0提问于2013-10-03得票数 1

回答已采纳

1回答

Unity3D: HighScore

unity3d

好的，我有一个关于团结的2d自上而下的游戏。我游戏的前提是在你死前收集尽可能多的硬币。我使用了球员预分配，这样当一个球员得到最高的分数时，它就可以保存这个人的分数。然而，我面临一个问题，那就是，当你第一次玩游戏的时候，你收集硬币然后死掉，然后把你得到的最高点保存下来，然后显示在一个面板上，但是如果你再次玩这个游戏，不收集任何硬币，那么游戏就不会显

浏览 2提问于2016-05-01得票数 1

回答已采纳

2回答

Python数学:如果数字介于

python

我目前正在学习Python，我的想法是将现有的Excel项目转换为web应用程序。该配置由400多个不同的许可证组成。我相信会有一个更有成效的方法来进行上述工作。非常感谢您的帮助。

浏览 0提问于2018-12-08得票数 0

回答已采纳

2回答

动态规划:在ProjectEuler上将自下而上的方法转换为自上而下的问题31

python、algorithm、dynamic-programming

为了学习，我想用自顶向下的DP来解决Euler项目上的问题.我已经用蛮力和自下而上的动态规划来解决它了。问题摘要:唯一组合的数量(顺序不重要)，其中和到‘t 2，有硬币1p，2p，5p，10p，20p，50p，gb1，gb2。我做了几次尝试，但我的结果确实考虑到了顺序。我试图通过包括一个"upperLimit“变量来排除这一点，它的工作是永远不要包含更有价值的硬币(消除像5,1,2,1，

浏览 4提问于2022-04-12得票数 1

回答已采纳

1回答

动态规划的复组合条件

algorithm、recursion、dynamic-programming、recurrence、coin-change

我正在探索一种动态规划设计方法是如何与问题的基本组合特性相关联的。如果我们遵循动态规划方法来设计一个算法来解决这个问题，它将允许一个多项式复杂度的解，我们将从这个问题以及它与

浏览 2提问于2018-02-15得票数 2

1回答

从不同的硬币组合(自上而下的方法)获得相同的数量

python、recursion、interview-questions、combinatorics

我正在读一个典型的面试问题在这里发现的。给定一个amount和一个denominations列表，计算出将amount分解成不同的硬币组合的可能方法的数量。这是我的Python解决方案。return _get_num_of_changes(amount, denominations) 这是一个自上而下的解决方案，从开始

浏览 0提问于2016-02-18得票数 6

2回答

自顶向下方法的硬币变化问题比较

python、algorithm、dynamic-programming

我正在研究LeetCode 322:硬币兑换。归还最少数量的硬币，你需要弥补这个数额。如果这个数额的钱不能由任何组合的硬币，回报-1。投入:硬币= 1,2,5，金额= 11说明: 11 =5+5+1 我选择一种<em

浏览 2提问于2021-09-27得票数 0

回答已采纳

1回答

最小硬币变化-动态规划

c++、algorithm、data-structures、dynamic-programming、coin-change

问题--你会得到不同面额的硬币和总金额。编写一个函数来计算所需硬币的最少数量，以弥补硬币的amount.Infinite供应。我的方法-我遵循了自上而下的方法，但通过使用map stl回忆录，我得到了TLE。请帮助找出错误和估计时间复杂性。这是我的密码- // for example coins v = {1,2} and W = 2 then

浏览 4提问于2020-03-14得票数 0

回答已采纳

1回答

动态规划的硬币换币算法

algorithm

我正在尝试一个微不足道的硬币更改问题-- #include <bits/stdc++.h>#define ll long long dp[0][0]=0; cout << Coi

浏览 4提问于2015-09-04得票数 3

回答已采纳

1回答

如何使二维球通过二维障碍物动画

java、javafx

我有一个JavaFX障碍课程，我的“硬币”是跌倒和到达底部。如果硬币撞上了障碍物，如果有空间，它要么向左，要么向右。当我运行我的程序时。硬币通过我的int数组通过正确的点。然而，硬币停留在屏幕上，没有完全的动画。所以，在硬币穿过<em

浏览 6提问于2022-04-04得票数 -2

点击加载更多