Redian新闻
>
another MIT dp problem without answer on their website.
avatar
another MIT dp problem without answer on their website.# JobHunting - 待字闺中
b*e
1
Bin Packing (Simplified Version). You have n1 items of size s1, n2 items of
size s2, and n3 items of size s3. You'd like to pack all of these items into
bins each of capacity C, such that the total number of bins used is
minimized.
avatar
b*e
2
my solution:
Recursive Function
Assume i > n1+n2 (can do same for i <= n1 and i > n1 and <= n1+n2)
Exist(i, j, a, b, c) = Exist(i-1, j, a, b, c) || Exist(i-1, j-Si, a, b, c-1)
where i is the index of ith item, j is the total capacity occupied by items
selected, a is the number of S1 item selected, b is the number of S2 item
selected, and c is the number of S3 item selected. note a <= n1, b<=n2 and c
<=n3.
Find all Exist from Exist(0,0,0,0,0) to Exist(n1+n2+n3, C, n1, n2, n3).
(a) If there is a j <= C which makes Exist(n1+n2+n3, j, n1, n2, n3) == ture,
the total number of bin used is 1.
(b) If there is no j satifisy (a), check whethere there is a j > C && j <=2c
which makes Exist(n1+n2+n3, j, n1, n2, n3) == true, then total number of
bin used is 2.
(c) do the same, if there is a j > 2c && <=3C, tototal numbe bin used is 3.
(d) continue .... until you find the min number of bins needed.
Above recursive function only tell us the min number of pins.
Introducing an intermediate matrix to track how to allocate the items.

of
into

【在 b*******e 的大作中提到】
: Bin Packing (Simplified Version). You have n1 items of size s1, n2 items of
: size s2, and n3 items of size s3. You'd like to pack all of these items into
: bins each of capacity C, such that the total number of bins used is
: minimized.

avatar
d*s
3
Is bin packing NP-Complete?

of
into

【在 b*******e 的大作中提到】
: Bin Packing (Simplified Version). You have n1 items of size s1, n2 items of
: size s2, and n3 items of size s3. You'd like to pack all of these items into
: bins each of capacity C, such that the total number of bins used is
: minimized.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。