C-01背包算法

一、实验目的

1、掌握C/C++语言的集成开发环境；

1、借助动态规划算法的示例程序，深入领会动态规划算法的核心理念；

2、通过应用动态规划算法解决实际问题，进一步增强对动态规划算法的理解与实践能力。

二、实验内容

1、动态规划算法思想：

将需要解决的问题划分为多个子问题，首先求解这些子问题，再根据子问题的解推导出原问题的解。与递归方法不同的是，动态规划在计算过程中会保存已求解过的子问题结果，避免重复计算。实现该方法的关键在于明确各个阶段子问题之间的递推关系：

（1）剖析原问题最优解所具备的性质，并描述其结构特征；

（2）建立最优值的递归表达式；

（3）按照自底向上的方式（由后向前）逐步计算最优值；

（4）结合在计算最优值过程中获取的信息，构建出完整的最优解。

2、0－1背包问题

设有n件物品以及一个容量为c的背包。第i件物品占据的空间为w[i]，其对应的价值为p[i]。目标是选择哪些物品放入背包中，使得总价值达到最大值。

代码：

 //物品数量:5

    
 //背包容量:承重20
    
 //定义重量:0  2  3  4  5   9
    
 //定义价值:0  3  4  5  8  10
    
 #include<stdio.h>
    
 int B[6][21] = { 0 }