Tag: 动态编程

硬币变化：动态编程

我编写的代码使用动态编程解决了基本的硬币更改问题，并提供了进行更改所需的最少硬币数量。 但是我希望将每个硬币播放部分的数量存储在最小数量中。 我要做的是初始化一个数组count[] ，就像散列一样，只要找到min ，就会增加coin[j]的数量，即count[coin[j]]++ 。 但这并不像我想要的那样工作，因为它每次找到与coin[j]相对应的min都会添加硬币。 因此，数字不是最终答案中硬币的最终计数。 这是代码： void makeChange(int coin[], int n, int value) { int i, j; int min_coin[MAX]; int min; int count[MAX]; min_coin[0] = 0; for (i=1; i <= value; i++) { min = 999; for (j = 0; j<n; j++) { if (coin[j] min_coin[i-coin[j]]+1) { min = min_coin[i-coin[j]]+1; count[coin[j]]++; } […]

动态规划问题..数组分区..

问题说， 给定一个大小为n的数组，我们必须将数组输出/分区为总和为N的子集。 For E,g, I/p arr{2,4,5,7}, n=4, N(sum) = 7(given) O/p = {2,5}, {7} 我在url动态编程3中看到了类似的问题/解释 我在pdf中有以下疑问： – 我们怎么能找到总和为N的子集，因为逻辑只告诉子集是否存在？ 另外，如果我们稍微改变一下这个问题，我们能否找到两个使用相同意识形态具有相同平均值的子集？ 任何人都可以对这个动态编程问题有所了解.. 🙂 提前致谢..

需要随机访问时改善随机存储器访问

我正在做的基本概念 完成联盟结构形成问题/组合拍卖。 给定一组N个代理，其中该代理集的不相交子集产生最佳结果。 例如， Agents = {a,b}及其值 {a} = 2 {b} = 3 {a,b} = 4 在这种情况下， {{a},{b}} = 5的联盟将给出最佳结果，其中它是{a,b}的成对不相交子集。 因此，简而言之，问题在于拆分集合并检查任何拆分总和是否大于原始集合。 （这部分与生成分裂以及如何表示数据一样好。） 我如何表示数据基本上是一个值数组，其中索引是设置配置（一个集合表示为整数）。 对于上面的例子： int val[4] = {0,2,3,4}其中set {a} = 01 = index 1 {b} = 10 = index 2 {a,b} = 11 = index 3 因此该集合充当值数组中的索引。 问题在于，这给出了随机存储器访问，给定了大量需要考虑2^n值的代理。 跳过这里的记忆访问问题 例如，在20个代理的环境中，给定两个元素10000000000000000001的集合，元素10000000000000000001的值是远离00000000000000000001的1048575个索引，其在内存中是4194300个字节，其表示32767个128字节距离的cachlines。 因此，可怕的访问模式。 我试过寻找的解决方案涉及按基数/汉明重量排序索引： 基于汉明重量的索引 确定两个整数之间的字典距离 遭受算术开销，我的计算将掩盖随机访问的惩罚。 […]

动态编程 – C中的最小硬币数

我已经浏览了网站上的各种问题，我没有设法通过以下推理找到任何实现这一点的东西（所以我希望这不是重复）。 我试图通过C程序解决的问题如下： 作为自动售货机控制器的程序员，您需要计算构成所需更改的最小硬币数量，以便回馈给客户。 这个问题的有效解决方案采用动态编程方法，首先计算1美分变化所需的硬币数量，然后计算2美分，然后计算3美分，直到达到所需的变化，并且每次使用先前计算的硬币数量。 编写一个包含函数ComputeChange()的程序，该函数获取有效硬币列表和所需的更改。 该程序应反复询问控制台所需的更改并相应地调用ComputeChange() 。 它还应该使用“缓存”，其中保留任何先前计算的中间值以用于后续查找。 在网上四处寻找其他人如何解决它后，我发现以下示例应用了便士，镍币和硬币： 我尝试以我的代码为基础。 但首先，我的代码并没有停止，其次，我不确定我是否合并了上面标题中提到的缓存元素。 （我不确定我需要怎么做这个部分）。 任何人都可以帮助我找到代码中的缺陷吗？ #include #include int computeChange(int[],int,int); int min(int[],int); int main(){ int cur[]={1,2,5,10,20,50,100,200}; int n = sizeof(cur)/sizeof(int); int v; printf(“Enter a value in euro cents: “); scanf(“%d”, &v); printf(“The minimum number of euro coins required is %d”, computeChange(cur, v, n)); return 0; } int computeChange(int […]

用于找到arrays中元素的最大总和以使得不多于k个元素相邻的算法

我遇到了这个问题。 给定一个仅包含正值的数组，您希望在约束条件下最大化所选元素的总和，使得多于k个选定元素的组不相邻。 例如，如果输入是1 2 3 1 7 9（n = 6且k = 2）。 输出将是21，它来自挑选元素_ 2 3 _ 7 9.我的简单DP解决方案就是这样 #include #include #include long maxsum(int n,int k,long *sums){ long *maxsums; maxsums = malloc(sizeof(long)*n); int i; long add = 0; for(i=n-1;i>=nk;i–){ add += sums[i]; maxsums[i] = add; } for(i = nk-1;i>=0;i–){ int j; long sum =0,max = 0,cur; […]

Bytelandian Gold Coin，动态编程，解释？

这有点不成熟，但我不得不问， 这里提到的Bytelandian金币问题 – http://www.codechef.com/problems/COINS/ ，据说是典型的DP问题，尽管我已经阅读了DP和递归的基础知识，但我发现很难理解它解， # include # include long unsigned int costArray[30][19]; unsigned int amount; unsigned int currentValue(short int factor2,short int factor3) { int j; unsigned int current = amount >> factor2; for(j=0;j<factor3;j++) current /= 3; return current; } long unsigned int findOptimalAmount(short int factor2,short int factor3) { unsigned int n = currentValue(factor2,factor3); if(n […]

编辑距离递归算法 – Skiena

我正在阅读Steven Skiena撰写的算法设计手册，我正在动态编程章节。 他有一些编辑距离的示例代码，并使用了一些既不在书中也不在互联网上解释的function。 所以我很想知道 a）该算法如何工作？ b）indel和match函数有什么作用？ #define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int string_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost […]

多序列的最长公共子序列

为了找到M = 2序列最长的研究，我做了很多研究，但我想弄清楚如何对M≥2序列进行研究 我被赋予N和M：M序列，具有N个独特元素。 N是{1 – N}的集合。 我已经考虑过动态编程方法，但我仍然对如何实际合并它感到困惑。 输入示例 5 3 5 3 4 1 2 2 5 4 3 1 5 2 3 1 4 这里可以看到最大序列 5 3 1 预期产出 Length = 3