精选优质文档-倾情为你奉上实验一 用动态规划解0-1背包问题1、 实验目的与要求 1、掌握动态规划算法求解问题的一般特征和步骤 2、使用动态规划法编程求解0/1背包问题。2、 实验内容 0-1背包问题(knapsack problem)：某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为C，C为一非负 数。目标是如何选择装入背包的物品使装入背包的物品总价值最大，所选商品 的一个可行解即所选商品的序列如何。背包问题与0-1 背包问题的不同点在 于：在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品 的全部。 三、问题描述 给定n和物品和一人背包，物品i的重量是wi，其价值为vi，问：如何选择装 入背包的物品，使得装入背包的物品的总价值最大。 举例: 若商店一共有5类商品，重量分别为：34789，价值分别为：45101113，则所选商品的最大价值为24， 所选商品的一个序列为0 0
