创意电子

标题: C++经典算法问题：背包问题（迭代+递归算法）！含源码示例 [打印本页]

---

作者: C语言编程    时间: 2021-10-5 19:01
标题: C++经典算法问题：背包问题（迭代+递归算法）！含源码示例

                               
登录/注册后可看大图

问题说明

有N件物品和一个容量为V的背包。
第i件物品的重量是w，代价是v。
求解将哪些物品装入背包可使这些物品的重量总和不凌驾背包容量，
且代价总和最大。
功能说明

本程序用动态规划的思想解决了背包问题，并用了两种算法： 迭代法、递归法。在迭代法中实现了打印背包问题的表格。
代码简述
通过用户输入数据，程序输入检测，动态分配空间，选择算法， 用动态规划的思想求解背包问题。
迭代法：
通过遍历n行W列，迭代每行每列的值，并把最优解放到 n行（在数组中为第n+1行）W列（在数组中为第W+1列）中。
递归法：
通过每次返回前i个物品和承重为j的最优解， 递归计算总背包问题的最优解。
源码示例

#include #include using namespace std;int **T = NULL;                // 存储背包问题表格的数组指针// 返回两个值的最大值int max(int a, int b) {        return (a > b) ? a : b;}// 迭代法，能显示背包问题的表格int packIterative(int n, int W, int *w, int *v) {                // 循环遍历n行        for (int i = 1; i

---

欢迎光临 创意电子 (https://wxcydz.cc/)

Powered by Discuz! X3.4