l********e
发帖数: 12 | 1 PHASE 1:一维
如果我有一个正整数N,有若干个小正整数n1,n2,n3,.....
我怎样挑出那些小的整数，使他们的和小于等于N,并且与N的差值最小。
PHASE 2:二维
如果我有一个MxN的大长方形，若干个Mi x Ni的小长方形，i=1,2,3,...,，请问如何选
择和排列这些小长方形，把它们放入那个大长方形，使剩余的面积最小？
以上所有数值为正整数。
Is it NP-hard problem? Any algorithm can solve it?
Thanks a lot. | z*l
发帖数: 30 | 2 quick ans to phase 1:
doable, suppose there're k numbers, n_1, n_2, ..., n_k.
compute (1+x^n_1)(1+x^n_2)...(1+x^n_k)
check the coefficients of the product polynomial.
Need to know the numbers being selected? Keep a trackback table.
phase 2: seems NP-hard. We need to select and PERMUTE.
【在 l********e 的大作中提到】
: PHASE 1:一维
: 如果我有一个正整数N,有若干个小正整数n1,n2,n3,.....
: 我怎样挑出那些小的整数，使他们的和小于等于N,并且与N的差值最小。
: PHASE 2:二维
: 如果我有一个MxN的大长方形，若干个Mi x Ni的小长方形，i=1,2,3,...,，请问如何选
: 择和排列这些小长方形，把它们放入那个大长方形，使剩余的面积最小？
: 以上所有数值为正整数。
: Is it NP-hard problem? Any algorithm can solve it?
: Thanks a lot.
| y***u
发帖数: 101 | 3
ft, 这不是穷举吗
两个都是NP-hard, reduction from Subset Sum.
何选
【在 z*l 的大作中提到】
: quick ans to phase 1:
: doable, suppose there're k numbers, n_1, n_2, ..., n_k.
: compute (1+x^n_1)(1+x^n_2)...(1+x^n_k)
: check the coefficients of the product polynomial.
: Need to know the numbers being selected? Keep a trackback table.
: phase 2: seems NP-hard. We need to select and PERMUTE.
| g*******g
发帖数: 18 | 4 两个都是NP-hard, reduction from Subset Sum.
PHASE 1:一维
it seems not NP hard.
PHASE is NP hard.
if not, just set N = 0, now, it is Subset Sum problem. |
|
