从列表a，b，c，d中查找具有最高属性x的唯一组合，并限制属性z的总和不超过一个值
我有4个列表（a，b，c，d）充满了相同类型的对象，看起来像这样：
public class Class
{
public double X
public double Z
}
我想做的是从每个列表中挑选一个项目，而x的最高总和是z的总和不超过设定值。
我为自己想出的唯一解决方案是通过创建所有组合的列表，然后从那里提取来强迫它。 在我当前的情况下，这可能是一个合理的解决方案，因为A，B，C，D每个均为100个项目，因此项目数量并不大。
但是我很好奇是否以及如何在较低的时间复杂性中“正确地”完成此操作。
编辑：添加示例。
列出每个项目。
A = [
AItem1 = { X = 1, Z = 1 },
AItem2 = { X = 2000, Z = 100}
]
B = [
BItem1 = { X = 200, Z = 20 },
BItem2 ={ X = 2000, Z = 1}
]
C = [
CItem1 = { X = 1, Z = 1 },
CItem2 = { X = 2000, Z = 1}
]
D = [
DItem1 = { X = 200, Z = 2 },
DItem2 = { X = 1, Z = 1}
]
查询：找到具有总和的最高总和的项目组合 z的不超过6。
结果：与查询项目组合的列表。
[AITEM1，BITEM2，CITEM2，DITEM1]
I have 4 lists (A,B,C,D) filled with the same type of object that looks something like this:
public class Class
{
public double X
public double Z
}
What I want to do is to pick out one item from each list, with the highest possible sum of X while the sum of Z does not exceed a set value.
The only solution I have figured out for myself is to brute force it by creating a list of all combinations and then extract from there.
This is might be a reasonable solution in my current case as A,B,C,D are all around 100 items each, so the number of items isn't insanely large.
But I am curious if and how this could be done "correctly" for a lower time complexity.
EDIT: Added example.
Lists with two items each.
A = [
AItem1 = { X = 1, Z = 1 },
AItem2 = { X = 2000, Z = 100}
]
B = [
BItem1 = { X = 200, Z = 20 },
BItem2 ={ X = 2000, Z = 1}
]
C = [
CItem1 = { X = 1, Z = 1 },
CItem2 = { X = 2000, Z = 1}
]
D = [
DItem1 = { X = 200, Z = 2 },
DItem2 = { X = 1, Z = 1}
]
Query: Find the combination of item with the highest sum of X with sum
of Z not exceeding 6.
Result: A list with the combination of items from query.
[AItem1, BItem2, CItem2, DItem1]
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
通常，这是一种 knapsack问题在大多数四个元素中，可能会有更多的限制被选择，每个元素必须来自单独的元素列表。
背包风格问题的标准类型是使用动态编程（请参见上面的Wikpedia链接中的更多），我认为这对您来说也很奏效。这将是伪多项式的，但通常会仔细编程很快。
另一个选择是使用某种组合求解器（混合整数编程，约束编程，SAT，...），但这可能是此问题的过高的。如果在良好的组合或解决方案上有更多的限制和/或更多选择，则可能会改变。
In general, this is a type of knapsack problem with the added restriction that at most four elements may be selected and that each element must be from a separate list of elements.
The standard type of algorithm for knapsack-style problems is to use dynamic programming (see more in the Wikpedia link above), which I think would work well for you case also. This will be pseudo-polynomial, but is often fast enough with some careful programming.
Another alternative would be to use a combinatorial solver of some kind (mixed integer programming, constraint programming, SAT, ...), but that is probably overkill for this problem. If there are more constraints and/or more choices on what is a good combination or solution, that may change.