问答题
考虑使用动态规划方法求解下列问题： 01背包数据如下表，求：能够放入背包的最有价值的物品集合。 
如设：V（i，j）——前i个物品中能够装入承重量j的背包中的最大总价值。请将如下递推式填写完整： 
自底向上：按行或列填写下表。 
发布日期：2020-12-11
试题解析
动态规划
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
- 中文名
- 动态规划
- 所属学科
- 运筹学
- 运用
- 求解决策过程（decision process）最优化的数学方法
- 分支
- 运筹学的一个分支
- 外文名
- Dynamic Programming
- 简称
- DP
- 第一本著作
- 《Dynamic Programming》
01背包
01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
- 中文名
- 01背包
- 条件
- M件物品取出若干放空间W的背包里
- 类别
- 数学问题，计算机问题
- 空间复杂度
- O(VN)
- 外文名
- 0-1 Knapsack
- 问题
- 求出获得最大价值的方案
- 时间复杂度
- O(VN)
求解
求解，汉语词汇，释义为请求解救或解除。
- 中文名
- 求解
- 释义
- 请求解救或解除
题王网让考试变得更简单
扫码关注题王，更多免费功能准备上线！
