r*******g
发帖数: 1335 | 1 9.7题，是不是它的解法有问题，step2明显应该用dp，他怎么就那么草率的找unfit
item?
谢了 |
l*********8
发帖数: 4642 | 2 你转帖一下题目和解答，可能会有更多人回复你。
【在 r*******g 的大作中提到】
: 9.7题，是不是它的解法有问题，step2明显应该用dp，他怎么就那么草率的找unfit
: item?
: 谢了
|
P**********c
发帖数: 3417 | 3 书上的解法是O(n^2)吧。DP比它快么？
【在 r*******g 的大作中提到】
: 9.7题，是不是它的解法有问题，step2明显应该用dp，他怎么就那么草率的找unfit
: item?
: 谢了
|
r*******g
发帖数: 1335 | |
d****z
发帖数: 53 | 5 这个应该用贪心就能得到最优解， 比如如果先用weight排序，然后做hight的时候先找
height最低，然后次低，然后。。。
证明跟introduction to algo书上，task scheduling的那个例子应该类似
【在 r*******g 的大作中提到】
: 9.7题，是不是它的解法有问题，step2明显应该用dp，他怎么就那么草率的找unfit
: item?
: 谢了
|
r*******g
发帖数: 1335 | 6 贪心不一定最优吧，假设先weight排序好，我们只看height，假设如下的hight
1,2,3,6,5,5.5,5.8
这个用贪心怎么求？明显结果是可选6个，但是如果简单把5设为unfit然后重新开始就
有问题。
【在 d****z 的大作中提到】
: 这个应该用贪心就能得到最优解， 比如如果先用weight排序，然后做hight的时候先找
: height最低，然后次低，然后。。。
: 证明跟introduction to algo书上，task scheduling的那个例子应该类似
|
x****1
发帖数: 118 | 7 我也和你想法一样，当时觉得有问题，跳过这道题了。
【在 r*******g 的大作中提到】
: 9.7题，是不是它的解法有问题，step2明显应该用dp，他怎么就那么草率的找unfit
: item?
: 谢了
|
P**********c
发帖数: 3417 | 8 恩，貌似是有问题。DP解法是longest increasing subsequence吗？
【在 r*******g 的大作中提到】
: 贪心不一定最优吧，假设先weight排序好，我们只看height，假设如下的hight
: 1,2,3,6,5,5.5,5.8
: 这个用贪心怎么求？明显结果是可选6个，但是如果简单把5设为unfit然后重新开始就
: 有问题。
|
