首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >基于项目出现次数百分比的N项集合查找算法

问基于项目出现次数百分比的N项集合查找算法
EN

Stack Overflow用户
提问于 2022-08-19 22:04:46
回答 2查看 62关注 0票数 1

假设我有不同颜色和大小的M盒。我需要找到一套N框,其中包含不同的颜色和大小组合。

例如,用户可以说,他们希望1500箱的桶中的20盒的最后一组包含20-80%的蓝色盒子,5%-30%的宽20英寸的盒子,100%的高20英寸的盒子“,只要最后一组20箱符合这三个限制条件,我就可以从1500箱的初始桶中挑出任何20箱。

这感觉就像背包问题,但我并不是百分之百相信是的。

EN

回答 2

Stack Overflow用户

发布于 2022-08-19 22:41:37

  • 首先,将桶大小缩小为与20“高度不匹配的盒子。

在其余的框中,创建4个桶:

  • 1:蓝色,20英寸宽
  • 2:非蓝色,20英寸宽
  • 3:蓝色,不20英寸宽
  • 4:非蓝色,不20英寸宽

F 213

满足以下条件:

  • C1: 4到16盒从桶1或3
  • C2: 1到6盒从桶1或2
  • C3: 20盒共从桶1,2,3,4

那么,不是最有效的,而是简单的:

代码语言:javascript
复制
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人都会导致大量无法核实的案件)。无论如何,创建一个涵盖“一般情况”的程序仍然是一个挑战--使用其他条件。

票数 0
EN

Stack Overflow用户

发布于 2022-08-19 23:36:41

一次,遍历M候选框的列表。

如果添加框符合总标准(见下文),则添加它。根据选定的框调整标准。

继续,直到找到N个箱子。

这并不一定是解决方案的终结,但如果存在解决方案,则很可能会结束。

没有解决办法是可能的。

条件:

  • 20-80%蓝色

  • 20-80%非蓝色

  • 5-30%为20“宽

”。

  • 70-95%不是20“宽

”。

  • 100%高20“。
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/73422658

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档