puppy love - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>pets - 心有所宠

puppy love

puppy love# pets - 心有所宠

b*i2014-02-04 08:02

1 楼

有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
有的盒子
比如 7*7 5*5, 4*6, 3*3
答案是7*7+4*6
感觉要用DP
求大牛给个解法

d*a2014-02-04 08:02

2 楼

我们跟着他喝点汤

r*l2014-02-04 08:02

3 楼

2600刀换地毯，先用10%哭胖，变2300多，然后掏出20张二手版买的2000多0.9肌肤卡,
hd mm问我"you just got married?". 肌肤卡输入很快，看着一张张卡进垃圾桶，感觉
很爽。
然后去lowes,买电炉子和kitchen sink/installation, 大概1000刀，又是10%+肌肤卡
。出门时候口袋都瘪了，终于不用担心肌肤卡有个什么闪失了.

m*f2014-02-04 08:02

4 楼

干活累死了，看看可爱的puppy~~~~

o*c2014-02-04 08:02

5 楼

为啥贪心不行？

g*u2014-02-04 08:02

6 楼

哭仙快沐浴吧，群众等着清水池汤呢!

G*s2014-02-04 08:02

7 楼

排包子

b*i2014-02-04 08:02

8 楼

我的爱拍被口水毁了。。。

【在 m*****f 的大作中提到】

: 干活累死了，看看可爱的puppy~~~~

b*i2014-02-04 08:02

9 楼

你这说的也有道理。。贪心貌似可以，因为这题是要求所有盒子都要放下去。

【在 o***c 的大作中提到】

: 为啥贪心不行？

n*e2014-02-04 08:02

10 楼

也是,市面上,肌肤卡算号器越来越多了...

m*g2014-02-04 08:02

11 楼

不，你不爱拍

【在 b********i 的大作中提到】

: 我的爱拍被口水毁了。。。

l*82014-02-04 08:02

12 楼

贪心就可以了吧。
把所有盒子按面积从大到小排序，对于当前盒子，找到最大的能fit的较小盒子，遍历
一遍应该就可以了。

【在 b******i 的大作中提到】

: 你这说的也有道理。。贪心貌似可以，因为这题是要求所有盒子都要放下去。

s*g2014-02-04 08:02

13 楼

人工能用肌肤卡给不？

m*f2014-02-04 08:02

14 楼

萌死啦，呆萌呆萌的，还笑哈哈的

【在 b********i 的大作中提到】

: 我的爱拍被口水毁了。。。

b*i2014-02-04 08:02

15 楼

我给你举个反例
有四个盒子，7*7, 9*5, 4*4, 8*1
我已经按照面积排过序了。前两个盒子自然都放在外面。第三个盒子按照你的说法应该
放在9*5里面，但8*1就要放在外面了。这不是最优的。
不是很懂你的最大的能fit的较小盒子是什么意思。

【在 l*****8 的大作中提到】

: 贪心就可以了吧。
: 把所有盒子按面积从大到小排序，对于当前盒子，找到最大的能fit的较小盒子，遍历
: 一遍应该就可以了。

m*j2014-02-04 08:02

16 楼

re

,

【在 r***l 的大作中提到】

: 2600刀换地毯，先用10%哭胖，变2300多，然后掏出20张二手版买的2000多0.9肌肤卡,
: hd mm问我"you just got married?". 肌肤卡输入很快，看着一张张卡进垃圾桶，感觉
: 很爽。
: 然后去lowes,买电炉子和kitchen sink/installation, 大概1000刀，又是10%+肌肤卡
: 。出门时候口袋都瘪了，终于不用担心肌肤卡有个什么闪失了.

b*i2014-02-04 08:02

17 楼

唉。。。都没机会看看小布对着一窝金毛puppy是啥反应。
试过几次，人家不乐意。。。

【在 m*****f 的大作中提到】

: 萌死啦，呆萌呆萌的，还笑哈哈的

s*z2014-02-04 08:02

18 楼

dp？
1 按照先w后h的方式排序
2 存每一次放完以后能下一次可以放的地方，应该是个arraylist；如果新来的可以fit
前面的某一个，就update那一个成这个新来的。如果新来的无法fit，就上一层
arraylist加一个新来的。
3 dp初始是无限大空间。
感觉还要做一遍先h后w？菜鸟轻拍。。