s******n
发帖数: 3946 | 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*****2
发帖数: 21240 | 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******n
发帖数: 3946 | 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*****2
发帖数: 21240 | 4
买机器也要花1000呀。
【在 s******n 的大作中提到】
: MinCost(1)为260？为啥阿，如果1年的话只修花60就行了。
|
s******n
发帖数: 3946 | 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*****2
发帖数: 21240 | 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****x
发帖数: 7404 | 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******n
发帖数: 3946 | 8 卖掉不是最优解啊。
一年卖掉800，还得花1000买入啊，净出200
一年不卖只修，净出60
【在 p*****2 的大作中提到】
: 卖机器还能得800呀。如果只用一年，肯定要卖掉呀。
|
|
p*****2
发帖数: 21240 | 9
我是说如果只用一年的话，你只有一个选择，1000买，维护60，卖掉800，没有其他选
择呀。
如果5年的话，按题目来说，我不是分了三种情况吗?
1. 一年卖掉
2. 两年卖掉
3. 三年卖掉
最后取最小的，就是最优。
【在 s******n 的大作中提到】
: 卖掉不是最优解啊。
: 一年卖掉800，还得花1000买入啊，净出200
: 一年不卖只修，净出60
|
s******n
发帖数: 3946 | 10 原题意思是，N年结束的时候还得保留1台机器，不能卖掉。
【在 p*****2 的大作中提到】
:
: 我是说如果只用一年的话，你只有一个选择，1000买，维护60，卖掉800，没有其他选
: 择呀。
: 如果5年的话，按题目来说，我不是分了三种情况吗?
: 1. 一年卖掉
: 2. 两年卖掉
: 3. 三年卖掉
: 最后取最小的，就是最优。
|
p*****2
发帖数: 21240 | 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***e
发帖数: 476 | 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 的大作中提到】
: 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?
|
