帮助解决背包算法 [英] Help solving Knapsack Algorithm

问题描述

大家好！
我需要一些帮助来解决C#中的算法.
背包算法(也称为帆布背包算法)是一个问题，其中
必须仅使用可从物品清单S中选择的一定数量的物品N包装一个具有一定重量W的背囊.
为了简化，列表S仅包含项目的权重.

值是:

Hi everybody!
I need some help solving an algorithm in C#.
The knapsack algorithm (also called Rucksack algorithm) is a problem in which
a rucksack has to be packed with a certain weight W using only a certain number of items N that can be choosen from a list of items S.
For simplification the list S only contains the weights of the items.

The values are:

W = 15
N = 17
S = [1, 2, 4, 9]

我需要有关如何在C#中解决此问题的帮助.

提前谢谢！

I need help in how to go about solving this problem in C#.

Thanks in advance!

推荐答案

好吧，这是一个有趣的问题.

首先，我怀疑这可能是一个 NP完全问题，但后来我怀疑我被误认为是因为某些后门"算法可能存在.但是，关于该问题的这篇文章指出它确实是W = 15, N = 17, S = [1, 2, 4, 9]?有了这个数字，从形式上来讲，不需要算法，经过验证的解决方案将是答案.

由于我在平安夜聚会后放松的心情并没有激发人们对使用通用算法工作的热情，因此''首先考虑一下有约束的正式解决方案.

好的，我们可以立即看到没有解决办法.
证明:当最小S = 1时，N个权重的最小总和等于N * 1 = N = 17，大于W = 15. -理解推断:如果N个权重的最小总和小于W，则N个权重的任何其他组合都大于W ＝>.没有N个权重的组合等于W => :thumbsdown:----;)

啊哈，现在我们可以看到查询者被锁定在角落里.我确实了解 shaden2009 可能犯了一个简单的错误；而数字可能会有所不同.谁知道?滑倒的手.可能是W和N应该互换；那么问题就可以解决...-为时已晚！出示证明，然后 shaden2009 无疑是诚实的人(我们都应该说实话，不是吗?)除了现在接受我的回答，别无选择.

如果对这个问题有更准确的表述，使之变得更加明智，我们当然会考虑考虑它(对吗?)，但这应该是另一个问题.目前的答案应该被接受；并结束了当前的问题.

感谢您的关注！
别紧张！ ;)
祝大家新年快乐！

Ok, this is a funny problem.

In first place, I suspected this could be a NP-complete problem but later I suspected I was mistaken because some "backdoor" algorithm might exist. However, this article on the problem states that it is indeed a NP-complete one. But only when I learned from the same article that there are different Knapsack and Knapsack-like problems, only then I paid closer attention to the formulation of the present Question. Silly me!

Well, this is neither basic nor generalized Knapsack problem, so let''s consider this is a Knapsack-like problem, rather simplified. The formulation is contradictory: the words "I need some help solving an algorithm in C#" hint that general algorithm is required, but is this case, why giving the following constraints: W = 15, N = 17, S = [1, 2, 4, 9]? With this figures, formally speaking, algorithm is not required, proven solution would be the answer.

As my mood of relaxing after the Christmas Eve party does not inspire much enthusiasm for working at the general algorithm, let'' first think about the formal solution with constraints.

Ok, we can immediately see that there is no solution.
The proof: as minimum S=1, minimum sum of N weights is equal to N*1 = N = 17, which is more than W = 15. Now, follow the most delicate and hard-to-understand inference: if minimum sum of N weights is less then W, any other combination of N weights is more than W => no combination of N weights is equal to W => :thumbsdown: ---- ;)

Aha, now we can see that the inquirer is locked in the corner. I do understand that shaden2009 could have done a simple mistake; and the figures could be different. Who knows? Slip of a hand. May be W and N should be swapped; then the problem is solvable... -- too late! The proof is presented, and shaden2009 assumed sole responsibility for the formulation of the problem.

In this way, shaden2009, being a undoubtedly, honest person (we all are supposed to be honest aren''t we?) has nothing to do but accept my answer now.

If there is more accurate formulation of the problem which would make it more sensible, we would certainly enjoy considering it (shall we?), but that should be another question. The present answer should be accepted; and the present question closed.

Thank you for attention!
Take it easy! ;)
Best wishes in New Year, everyone!

这篇关于帮助解决背包算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！