基本信息

---

下载

文档摘要

---

假设一个飞檐走壁的小偷，背着一个可装磅东西的背包，潜入一个房间，可以

如下三件商品。

为了让的商品价值最高，你应该哪些商品？最简单的算法：尝试各种可

能的商品组合，并找出价值最高的组合。

方案虽然可行，但是效率非常低！如果3件商品，需要计算8种组合情况，4件商品，

需要计算16种组合情况，n件商品，一共2的n次方种情况。那么，如何找到最优

解？使用动态规划!动态规划算法原理：先解决子问题，再逐步解决大的问题。对

于背包问题，先解决（子背包）问题！

网格解题（初始状态为空）：

吉他行：

音响行：

笔记本电脑行：

【题目描述】

一个旅行者有一个最