也来发个经典的dynamic programming问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

也来发个经典的dynamic programming问题

也来发个经典的dynamic programming问题# JobHunting - 待字闺中

s*n2011-11-27 08:11

1 楼

Equipment Replacement
Suppose a shop needs to have a certain machine over the next five year
period. Each new machine costs $1000. The cost of maintaining the machine
during its ith year of operation is as follows: m1=60, m2=80, m3=120. A
machine may be kept up to three years before being traded in. The trade in
value after i years is s1=800, s2=600, s3=500. How can the shop minimize
costs over the five year period?

p*22011-11-27 08:11

2 楼

int MinCost(int years)
{
if(years==0)
return 0;
int c1,c2,c3 = MAX_INT;
c1=1000-800+60+MinCost(years-1);
if(years>=2)
c2=1000-600+60+80+MinCost(years-2);
if(years>=3)
c3=1000-500+60+80+120+MinCost(years-3);
return min(c1,c2,c3);
}
用hashtable可以cache吧。

s*n2011-11-27 08:11

3 楼

MinCost(1)为260？为啥阿，如果1年的话只修花60就行了。

【在 p*****2 的大作中提到】

: int MinCost(int years)
: {
: if(years==0)
: return 0;
: int c1,c2,c3 = MAX_INT;
: c1=1000-800+60+MinCost(years-1);
: if(years>=2)
: c2=1000-600+60+80+MinCost(years-2);
: if(years>=3)
: c3=1000-500+60+80+120+MinCost(years-3);

p*22011-11-27 08:11

4 楼

买机器也要花1000呀。

【在 s******n 的大作中提到】

: MinCost(1)为260？为啥阿，如果1年的话只修花60就行了。

s*n2011-11-27 08:11

5 楼

你再看看？第一年应该是60，如果买机器加上去也是1060，怎么会出来260？
int MinCost(int years)
{
if(years==0)
return 0;
if (years==1) {
// 换,修
return min(1000-800,60)
} else if (years==2) {
// 换+MinCost(1)，修修，修换
return min(100-800+MinCost(1), 60+80, 60+(1000-600));
} else if (years=3) {
// 换+MinCost(2)，修修修，修修换，修换+MinCost(1)
return min(1000-800+MinCost(2), 60+80+120, 60+80+(1000-500), 60+(1000
-600)+MinCost(1));
} else {
// 修修换+MinCost(years-3)，修换+MinCost(years-2)，换+MinCost(years-
1)
return min(60+80+(1000-500)+MinCost(years-3), 60+(1000-600)+MinCost(
years-2), (1000-800)+MinCost(years-1));
}
}

p*22011-11-27 08:11

6 楼

卖机器还能得800呀。如果只用一年，肯定要卖掉呀。

【在 s******n 的大作中提到】

: 你再看看？第一年应该是60，如果买机器加上去也是1060，怎么会出来260？
: int MinCost(int years)
: {
: if(years==0)
: return 0;
: if (years==1) {
: // 换,修
: return min(1000-800,60)
: } else if (years==2) {
: // 换+MinCost(1)，修修，修换

q*x2011-11-27 08:11

7 楼

不会是面试题吧。

【在 s******n 的大作中提到】

: Equipment Replacement
: Suppose a shop needs to have a certain machine over the next five year
: period. Each new machine costs $1000. The cost of maintaining the machine
: during its ith year of operation is as follows: m1=60, m2=80, m3=120. A
: machine may be kept up to three years before being traded in. The trade in
: value after i years is s1=800, s2=600, s3=500. How can the shop minimize
: costs over the five year period?

s*n2011-11-27 08:11

8 楼

卖掉不是最优解啊。
一年卖掉800，还得花1000买入啊，净出200
一年不卖只修，净出60

【在 p*****2 的大作中提到】

: 卖机器还能得800呀。如果只用一年，肯定要卖掉呀。

p*22011-11-27 08:11

9 楼

我是说如果只用一年的话，你只有一个选择，1000买，维护60，卖掉800，没有其他选
择呀。
如果5年的话，按题目来说，我不是分了三种情况吗?
1. 一年卖掉
2. 两年卖掉
3. 三年卖掉
最后取最小的，就是最优。

【在 s******n 的大作中提到】

: 卖掉不是最优解啊。
: 一年卖掉800，还得花1000买入啊，净出200
: 一年不卖只修，净出60

s*n2011-11-27 08:11

10 楼

原题意思是，N年结束的时候还得保留1台机器，不能卖掉。

【在 p*****2 的大作中提到】

:
: 我是说如果只用一年的话，你只有一个选择，1000买，维护60，卖掉800，没有其他选
: 择呀。
: 如果5年的话，按题目来说，我不是分了三种情况吗?
: 1. 一年卖掉
: 2. 两年卖掉
: 3. 三年卖掉
: 最后取最小的，就是最优。

p*22011-11-27 08:11

11 楼

不对吧？没看到有这个意思。就是说需要5年，5年之后可不管了，没说还继续要呀。
为了降低cost，当然要卖了。
Suppose a shop needs to have a certain machine over the next five year
period.
就说用5年呀。没说五年之后还要保留一台。

【在 s******n 的大作中提到】

: 原题意思是，N年结束的时候还得保留1台机器，不能卖掉。

H*e2011-11-27 08:11

12 楼

能给个答案吗？
我是这么想的：
定义 M[j,k]为在这种情况下的最小值：第j年末尾机器有k年的年纪，也就是说如果M
[5,1]说明在第五年的机器是新买的。
M[j,k] = M[j-1, k-1] + V(k) , if k!=1
＝ min_over_year( M[j-1, year) + 1000 - T(year)) ) if k==1
case1 为假设机器是从去年过渡来的，没买新的， V(k)是maintein的花费
case2 是假设买新的，那么T(year)为老机器trade in的价格， year为去年机器的年纪
，1=最后min over M[5,k], 1<=k<=3.

【在 s******n 的大作中提到】