问题 您将如何解决这个问题?

斯丹尼古

成员
已加入
五月17,2019
留言内容
7
编程经验
Beginner
您好,我刚刚开始学习C#,并且遇到了要解决的问题。

鉴于:
目标重量(体重
两种不同的权重(任意多)

问题:
使用权重之一或两者,最接近目标权重的是什么?

要求的输出:
使用最接近的砝码和每个砝码的数量。

例如:给定的TargetWeight为230克,两个权重为170克和40克。这些重量的哪种组合最接近230克?

我已经挣扎了两天。任何帮助将不胜感激。

谢谢。
 

斯丹尼古

成员
已加入
五月17,2019
留言内容
7
编程经验
Beginner
谢谢,但我看不到这种关系。
根据硬币问题(只要硬币面额没有 共同除数 greater than 1):
硬币1-17,硬币2-4。"coins" is 47.
我的问题:
重量1-17,重量2-4。目标重量22.如果x的重量为17,y的重量为4至22,我能得到的壁橱重量是多少?从逻辑上讲,我会说21,但是我需要为任何数字编写代码。

:凉爽的:
 

斯丹尼古

成员
已加入
五月17,2019
留言内容
7
编程经验
Beginner
的确可以,但是,您在低于TargetWeight和最小权重数方面就限制了该问题,因此解决方案变得容易。我的问题没有条件。我实际上了解算法。我的问题是将其溢出到C#中。
 

跳伞者

工作人员
已加入
2019年4月6日
留言内容
2,612
地点
弗吉尼亚州切萨皮克
编程经验
10+
您的问题就是背包问题。您在说哪种算法?
 

跳伞者

工作人员
已加入
2019年4月6日
留言内容
2,612
地点
弗吉尼亚州切萨皮克
编程经验
10+
是的。对您的问题不一样吗?您有两类特定重量的物品。您需要弄清楚每个项目中有多少个项目的总和接近或等于目标重量。
 

跳伞者

工作人员
已加入
2019年4月6日
留言内容
2,612
地点
弗吉尼亚州切萨皮克
编程经验
10+
因此,您说的是给定权重3和5,目标权重4,则正确答案可以是3或5。而目标权重为14的正确答案可以是5 * 2 + 3或5 * 3?那么对于17正确的答案是什么?
 

跳伞者

工作人员
已加入
2019年4月6日
留言内容
2,612
地点
弗吉尼亚州切萨皮克
编程经验
10+
In your shoes, the way I would tackle this problem is first find a UKP solution for less than or equal to the target weight. Call this solution1. If solution1 equal to the target, then you are done. Otherwise, solve for the UKP's of target + 1 to 2 * target - solution1 - 1. When you get a solution that is less than abs(target - solution1) then you have your answer. If you can't find a solution less than abs(target - solution1), then solution1 is (one of) the best answer(s) you can get.
 
Last edited:
最佳 底部