i***q
发帖数: 1095 | 1 背包问题的变种，商品变成了房子，房子有不同种类，售价不同，租金不同，同类型的
房子，起始价格一样，每买一栋会上涨一定的价钱，然后拥有了房子能收租金，给定
budget然后求一个最优化的购买方案。
dp的话状态过多，觉得不对，最后用贪心做的，觉得不对，高手们给谈谈思路？ |
g**e
发帖数: 6127 | 2 sounds like a linear optimization problem. |
C***U
发帖数: 2406 | 3 但是离散的 房子要整栋的
【在 g**e 的大作中提到】
: sounds like a linear optimization problem.
|
j******y
发帖数: 2578 | 4 integer programming
【在 C***U 的大作中提到】
: 但是离散的 房子要整栋的
|
C***U
发帖数: 2406 | 5 ok
【在 j******y 的大作中提到】
: integer programming
|
c********t
发帖数: 5706 | 6 最后结果是要买到最多的房子，还是要租金最多？
【在 i***q 的大作中提到】
: 背包问题的变种，商品变成了房子，房子有不同种类，售价不同，租金不同，同类型的
: 房子，起始价格一样，每买一栋会上涨一定的价钱，然后拥有了房子能收租金，给定
: budget然后求一个最优化的购买方案。
: dp的话状态过多，觉得不对，最后用贪心做的，觉得不对，高手们给谈谈思路？
|
i***q
发帖数: 1095 | 7 我觉得不是，某类房子如果买k栋，总价是k的二次函数，不是线性函数，当然二次一样
可以规划，只是觉得这些人为什么要在编程面试里边考这个，如果是找实数解，还有解
法，但是如果是整数解，肯定是np hard，当然人家既没有说不是np hard，也没说要
optimal，所以可能是我多心了。
【在 g**e 的大作中提到】
: sounds like a linear optimization problem.
|
i***q
发帖数: 1095 | 8 租金最多
【在 c********t 的大作中提到】
: 最后结果是要买到最多的房子，还是要租金最多？
|
h*******e
发帖数: 1377 | 9 枚舉 同種類 房子個數 0 到最值。 同種類只能買一組房子。然後 背包問題dp求解
。 |
h*******e
发帖数: 1377 | 10 這道題按理說太難了。。 據說當年一小牛第一次見這類題， 寫了200多行的程序 一分
沒得。。 |
i***q
发帖数: 1095 | 11 sounds like a working plan, thanks
【在 h*******e 的大作中提到】
: 這道題按理說太難了。。 據說當年一小牛第一次見這類題， 寫了200多行的程序 一分
: 沒得。。
|
