给定整数和阈值T的集合,将该集合分成尽可能多的组,其和> = T

问题描述 投票:1回答:1

给出一个整数和阈值T的集合,将该集合分成总和> = T的尽可能多的组。

剩余的整数(其总​​和

约束:

  • 列表长度<= 1,000
  • 值和T <= 1,000,000

多项式时间内是否有针对此问题的算法?

例如,给定[25,25,25,50,50,50,10]和阈值T = 70,它应该返回:

[25,50]
[25,50]
[25,50]
Remaining: [10]

选择[25,25,25]作为组之一将使得可以仅再形成一个组[50,50],其余值为[50,10]。两组不是最佳的组数量,这就是为什么此解决方案不正确的原因。

algorithm time-complexity knapsack-problem np
1个回答
0
投票

没有多项式时间算法,因为它在特殊情况下包含np-complete Partition problem

© www.soinside.com 2019 - 2024. All rights reserved.