[理工] 102成大资工程式设计 entryword PTT批踢踢实业坊

楼主: entryword (chiahua) 2014-02-21 16:07:45

http://ppt.cc/WcTN
二、计算题的第2小题
题意看不太懂
(a)我理解是此问题转成recursion tree后总共有几个node
(b)就真的看不懂了, 什么叫有几个最佳化的选择
有人知道吗?
谢谢QQ

作者: kiki86151 (鲁饭) 2014-02-21 16:28:00

DynamicProgramming的面值问题http://ppt.cc/H8Qb 算法笔记很清楚简单来说有8元可以换1,4,6 换最少的数为多少最佳解结构就是先8元换1 8元换4 8元换6 观察哪个最少可以推到递回

作者: john2557 (Wanger) 2014-02-21 16:46:00

所以这一题是要写algo而已吗？

作者: kiki86151 (鲁饭) 2014-02-21 17:58:00

差不多吧反正懂后就嘴砲而已 M就是总钱数(8) 那个c代表有d(1,4,6)面值可换 i指那些面值可换的数要换最少(4*2)

楼主: entryword (chiahua) 2014-02-21 19:04:00

我是不知道a, b小题要回答什么@@这题不是问算法吧不过写上去大概还是有一点分?

作者: WashFreeID (免洗) 2014-02-21 19:34:00

第一题是M?第二题d-1? 不确定

作者: kiki86151 (鲁饭) 2014-02-21 19:46:00

第一题感觉比较复杂不是M吧应该要画递回树第二题我觉得是d 就是选M-c1,M-c2....M-cd这些子问题最小在+1而已找到一个有实作code类似的网站http://ppt.cc/CT5l 它那颗树就是5换1,2,3子问题就是树的node 只有3换1出现2次

作者: jeremy4849 (yang) 2014-02-22 00:00:00

第一题有different ，感觉是M-1

继续阅读