假设我有不同颜色和大小的M盒。我需要找到一套N框,其中包含不同的颜色和大小组合。
例如,用户可以说,他们希望1500箱的桶中的20盒的最后一组包含20-80%的蓝色盒子,5%-30%的宽20英寸的盒子,100%的高20英寸的盒子“,只要最后一组20箱符合这三个限制条件,我就可以从1500箱的初始桶中挑出任何20箱。
这感觉就像背包问题,但我并不是百分之百相信是的。
发布于 2022-08-19 22:41:37
在其余的框中,创建4个桶:
F 213
满足以下条件:
那么,不是最有效的,而是简单的:
int b1, b2, b3, b4;
int B1 = size_of_bucket_1;
int B2 = size_of_bucket_2;
int B3 = size_of_bucket_3;
int B4 = size_of_bucket_4;
for(b1=0; b1<=6; b1++)
{
for(b2=0; b2<=6; b2++)
{
for(b3=0; b3<=16; b3++)
{
if(b1<=B1 &&
b2<=B2 &&
b3<=B3 &&
b4<=B4 &&
b1+b2>=1 && b1+b2<=6 &&
b1+b3>=4 && b1+b3<=16 &&
b1+b2+b3<=20 && b4>=20-b1-b2-b3)
{
// Debug Solution Print
// printf("%i %i %i %i\n", b1, b2, b3, 20-b1-b2-b3);
return true; // Match found
}
}
}
}
return false; // No match possible共7*7* 17 = 833例检查。这是不算太坏的,因为它从1500中选择了任意20个框。(可以减少要检查的情况数,在外部循环中使用b1修复,可以减少内环( b2和b3的间隔)。)
对于更一般的情况,(其他条件),但是有4个桶和20个盒子可供选择: 21 * 21 * 21 * 21 = 194481的检查通常仍然足够好。不管怎么说,事实上,由于总共有20个箱子,所以只有21 * 21 * 21 = 9261箱。
根据这一点,从数学的角度来看,问题可以减少,如果有匹配的话,只需要检查一些有用的情况。( 1500人中的任何20人都会导致大量无法核实的案件)。无论如何,创建一个涵盖“一般情况”的程序仍然是一个挑战--使用其他条件。
发布于 2022-08-19 23:36:41
一次,遍历M候选框的列表。
如果添加框符合总标准(见下文),则添加它。根据选定的框调整标准。
继续,直到找到N个箱子。
这并不一定是解决方案的终结,但如果存在解决方案,则很可能会结束。
没有解决办法是可能的。
条件:
”。
”。
https://stackoverflow.com/questions/73422658
复制相似问题