计算机问题求解一论题3-1 动态规划 2020年09月15日
计算机问题求解 – 论题3-1 - 动态规划 2020年09月15日
Rod Cutting Problem The rod-n proble is the following.Given a rod of lengthninches and a table of prices pi for i=1,2..determine the maximum revenueobtain- able by ctin up the rod and selling the pieces. 一个样本输 入及其解： length i 1234567 89 10 price Pi 1589101717 202430 r=1 from solution 1=1 (no cuts), r6 17 from solution 6=6 (no cuts), r2=5 from solution 2=2 (no cuts), 7=18 from solution 7 =1+6 or 7=2+2+3, r3 =8 from solution 3=3 (no cuts), rs 22 from solution 8=2+6. r4 10 from solution 4=2+2, r9 25 from solution 9=3+6, rs 13 from solution 5=2+3, rio 30 from solution 10=10 (no cuts). f
Rod Cutting Problem 一个样本输 入及其解： r7 :
问题1： 这个问题的解空间有多 大？为什么？
问题2 如何搜索？可以压缩解空间吗？ 似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样
似乎任何一个可行解， 都可能是最优解 和我们之前看到的“猜年龄”、“求直径”似乎都不一样
间题3：如何思考？ 第一刀切下去之后： 针对任意的r,我们能够写出下面的公式！ Tn=ri+rn-i 当i从1递增到-1时，我们找到了一个遍历解空间的科学手法
rn : i rn =ri+rn-i 第一刀切下去之后： 针对任意的rn，我们能够写出下面的公式！ 当i从1递增到n-1时，我们找到了一个遍历解空间的科学手法