从多个计数约束中提取可能的样品组合
我有一些类似的输入数据。
| 唯一ID | Q1 | Q2 | Q3 |
|---|---|---|---|
| 1 | 1 1 | 2 | 2 |
| 1 | 1 | 2 | 3 |
| 1 | 0 | 3 | 4 |
| 2 | 0 | 1 | 5 |
| 3 | 1 | 2 | 6 |
| 4 | 1 | 3 | ， |
我的目标是提取一些满足以下条件的数据：
- 总计数：4
> q1 = 1计数：2q1 = 2计数：1q2 = 1计数：1〜3q3 = 1计数： 1
在这种情况下，两个具有IDS [1、2、4、5]或[2、3、4、5]的数据集都是可接受的答案。
实际上，我可能会拥有6000多行数据，最多12个计数限制。计数可能从1到50不等。 我编写了一个解决方案，该解决方案首先将所有ID按每个条件分组，然后使用DEAPTH首次搜索来耗尽地尝试组之间的所有可能组合。 （我相信这是一个蛮力的解决方案...） 但是，我总是用完计算机的内存和时间，然后才能得到一个可能的答案。
我的问题是，
- 这个问题可能最少的时间复杂性是什么？ （我相信这是一个子集总问题，但我不确定）
- 如何解决这个问题而不是蛮力的问题？我正在考虑动态编程或决策树。但是，我相信我可能会使用其中的任何一个都用完计算机的内存。还是我可以通过每个数据行的概率/熵来解决此问题（我是否会感谢有关此问题的更多详细信息）？
我的蛮力解决方案示例代码根本不值得阅读。因此，我会跳过发布我的代码片段...
I have some input data like this.
| unique ID | Q1 | Q2 | Q3 |
|---|---|---|---|
| 1 | 1 | 1 | 2 |
| 2 | 1 | 1 | 2 |
| 3 | 1 | 0 | 3 |
| 4 | 2 | 0 | 1 |
| 5 | 3 | 1 | 2 |
| 6 | 4 | 1 | 3 |
And my target is to extract some data which satisfy the following conditions:
- total count: 4
Q1=1count: 2Q1=2count: 1Q2=1count: 1~3Q3=1count: 1
In this case, both data set with ids [1, 2, 4, 5] or [2, 3, 4, 5] are acceptable answers.
In reality, I will possibly have 6000+ rows of data and up to 12 count limitation like above. The count might varies from 1 to 50.
I've written a solution which firstly group all ids by each condition, then use deapth first search to exhaustedly try out all possible combinations between the groups. (I believe this is a brute-force solution...)
However, I always run out my computer's memory and my time before I can get a possible answer.
My question is,
- what's the possible least time complexity of this problem. (I believe this is kind of subset sum problem, but I am not sure)
- how can I solve this problem instead of a brute-force one? I'm considering dynamic programming or decision tree. However, I believe that I will possibly run out of my computer's memory with either of this one. Or can I solve this problem by each data row's probabilities/entropy (and I would appreciate more details on this)?
My brute-force solution sample codes are not worth reading at all. Thus, I'll skip posting my code snippets...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论