找到携带的最大重量子集

一个人的物品重量低于其重量。找到携带的最大重量子集

[10,10,12,15,16,20,45,65,120,140,150,178,198,200,210,233,298,306,307,310,375,400,420 ，411，501，550，662，690，720，731，780，790]

他可以带回家的最大重量是3公斤（3000克）。他希望尽可能多地注意。

注意我尝试了回溯算法，但它给了我等于我正在寻找的总和的子集，但是在我无法找到相等匹配总和的情况下，那么它失败了。我想找到接近总和的子集。

来源

2015-02-11 Venkata Krishna

为什么不记录当前最佳结果，如果当前值和目标之间的差值小于以前的最佳结果，则遍历并更新该值？ – 2015-02-11 12:20:17

这是subset sum problem是solveable在Dynamic Programming - 这基本上是一种有效的实现您的回溯一个，按照下面的递推公式：

D(0,n) = True 
D(x,0) = False | x > 0 
D(x,n) = D(x-arr[i], n-1)   OR  D(x,n-1) 
      ^       ^
     item i is in subset   item i is not in subset

通过采用自下而上的动态规划（创建一个矩阵并从低到高填充）或自上而下的动态规划（记忆每个结果并检查它是否已在递归之前计算），这可在O(n*W)中解决，其中n是元素的数量，W是子集的大小（ 3000你的情况）。

如果您运行自下而上的DP，则最大值为x，因此D(x,n) = True是可承载的最大权重。为了找到实际项目，应该按照表格回来，检查在每个决策点添加了哪些项目，并产生添加的项目。返回实际集合在线程中更详细地解释：How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?（此线程处理背包问题，这是您的问题的一个变体，每个项目的重量=成本）

来源

2015-02-11 12:18:15 amit

有趣的一面你回答：你有没有任何参考，在递归与memoization一起被称为“自上而下的动态规划”？我多年来一直在考虑这是否被认为是动态编程，或者“动态编程”意味着根本没有执行递归调用。 – Codor 2015-02-11 12:34:24

@Codor虽然它不是一个权威，但是[wikipedia page]（http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming）使用这个术语： – amit 2015-02-11 12:40:01

'自上而下的方法：这是直接失败任何问题的递归表述。如果任何问题的解决方案可以使用其子问题的解决方案递归制定，并且如果其子问题重叠，则可以轻松地将解决方案存储或存储在表中的子问题的解决方案中。每当我们试图解决一个新的子问题时，我们首先检查该表是否已经解决。如果解决方案已经记录下来，我们可以直接使用它，否则我们解决子问题并将其解决方案添加到表格中。' – amit 2015-02-11 12:40:31

使用回溯，我们可以构建这样的解决方案，
我们将尝试返回这是最近的，但使用这种伪码给定的重量也降低了子集的最大重量：

func(weight_till_now,curr_pos) 
    if(weight_till_now > max_possible) return 0 
    if(curr_pos >= N) return 0 

    // Taking this weight in current subset 
    weight = max(weight_till_now,func(weight_till_now+wt[curr_pos],curr_pos+1)) 

    // Not taking in current subset 
    weight = max(weight_till_now,func(weight_till_now,curr_pos+1)) 

    return weight

调用带有初始参数此功能将0,0给你的答案，因为这将使每个子集，并尝试获得所有可能的子集权重的最大权重，如果它是大于最大可能的重量，那么这将返回0.

来源

2015-02-11 12:53:29

找到携带的最大重量子集

回答

相关问题