手提袋创意平面，有点儿意思。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

手提袋创意平面，有点儿意思。

手提袋创意平面，有点儿意思。# Joke - 肚皮舞运动

i*q2012-07-31 07:07

1 楼

背包问题的变种，商品变成了房子，房子有不同种类，售价不同，租金不同，同类型的
房子，起始价格一样，每买一栋会上涨一定的价钱，然后拥有了房子能收租金，给定
budget然后求一个最优化的购买方案。
dp的话状态过多，觉得不对，最后用贪心做的，觉得不对，高手们给谈谈思路？

i*f2012-07-31 07:07

2 楼

见到有很多16x16的，有人说小。目前只换135的卷，该买多大的？

c*72012-07-31 07:07

3 楼

=.=

g*e2012-07-31 07:07

4 楼

sounds like a linear optimization problem.

r*e2012-07-31 07:07

5 楼

不错

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

: =.=

C*U2012-07-31 07:07

6 楼

但是离散的房子要整栋的

【在 g**e 的大作中提到】

: sounds like a linear optimization problem.

j*y2012-07-31 07:07

7 楼

integer programming

【在 C***U 的大作中提到】

: 但是离散的房子要整栋的

C*U2012-07-31 07:07

8 楼

ok

【在 j******y 的大作中提到】

: integer programming

c*t2012-07-31 07:07

9 楼

最后结果是要买到最多的房子，还是要租金最多？

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

: 背包问题的变种，商品变成了房子，房子有不同种类，售价不同，租金不同，同类型的
: 房子，起始价格一样，每买一栋会上涨一定的价钱，然后拥有了房子能收租金，给定
: budget然后求一个最优化的购买方案。
: dp的话状态过多，觉得不对，最后用贪心做的，觉得不对，高手们给谈谈思路？

i*q2012-07-31 07:07

10 楼

我觉得不是，某类房子如果买k栋，总价是k的二次函数，不是线性函数，当然二次一样
可以规划，只是觉得这些人为什么要在编程面试里边考这个，如果是找实数解，还有解
法，但是如果是整数解，肯定是np hard，当然人家既没有说不是np hard，也没说要
optimal，所以可能是我多心了。

【在 g**e 的大作中提到】

: sounds like a linear optimization problem.

i*q2012-07-31 07:07

11 楼

租金最多

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

: 最后结果是要买到最多的房子，还是要租金最多？