C++经典算法问题：背包问题（迭代+递归算法）！含源码⽰
例
问题说明
有N件物品和⼀个容量为V的背包。
第i件物品的重量是w[i]，价值是v[i]。
求解将哪些物品装⼊背包可使这些物品的重量总和不超过背包容量，
且价值总和最⼤。
功能说明
本程序⽤动态规划的思想解决了背包问题，并⽤了两种算法： 迭代法、递归法。在迭代法中实现了打印背包问题的表格。
代码简述
通过⽤户输⼊数据，程序输⼊检测，动态分配空间，选择算法， ⽤动态规划的思想求解背包问题。
迭代法：
通过遍历n⾏W列，迭代每⾏每列的值，并把最优解放到 n⾏（在数组中为第n+1⾏）W列（在数组中为第W+1列）中。
递归法：
通过每次返回前i个物品和承重为j的最优解， 递归计算总背包问题的最优解。
源码⽰例
#include <iostream>
#include <algorithm>
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⾏
// 循环遍历n⾏
for (int i = 1; i <= n; ++i)
{
// 循环遍历W列
for (int j = 1; j <= W; ++j)
{
//第i个物品能装下，则⽐较包括第i个物品和不包括第i个物品，取其最⼤值
if (w[i] <= j)
T[i][j] = max(v[i] + T[i - 1][j - w[i]], T[i - 1][j]);
// 第i个物品不能装下，则递归装i-1个
else
T[i][j] = T[i - 1][j];
}
}
return T[n][W];
}
// 递归法，不⽀持显⽰背包问题的表格
int packRecursive(int n, int W, int *w, int *v) {
// 结束条件（初始条件），i或者j为0时最⼤总价值为0
if (n == 0 || W == 0) {
return 0;
}
// 第i个物品不能装下，则递归装i-1个
if (w[n] > W) {
return packRecursive(n - 1, W, w, v);
}
//第i个物品能装下，则⽐较包括第i个物品和不包括第i个物品，取其最⼤值
else {
return max(v[n] + packRecursive(n - 1, W - w[n], w, v), packRecursive(n - 1, W, w, v)); }
}
// 打印背包问题的表格
void printT(int n, int W)
{
// 打印n⾏
for (auto i = 0; i <= n; i++)
{
// 打印⾏数
cout << i << ":\t";
// 打印W列
for (int w = 0; w <= W; w++)
{
cout << T[i][w] << "\t";
}
/
/ 换⾏
cout << endl;
}
}
int main() {
int *w = NULL;  // 存储每件物品重量的数组指针
int *v = NULL;  // 存储每件物品价值的数组指针
int n;    // 物品个数n
int W;    // 背包总承重W
cout << "---------------- 背包问题 ----------------" << endl;
cout << "请输⼊物品数 n (n>=0) " << endl;
/
/ 输⼊背包数
cin >> n;
if (cin.fail() || n < 0)
{
cout << "输⼊n错误！" << endl;
system("pause");
return 0;
}
cout << "请输⼊背包承重量 W (W>=0) " << endl;
// 输⼊背包承重量
cin >> W;
if (cin.fail() || W < 0)
{
cout << "输⼊W错误！" << endl;
system("pause");
return 0;
}
// 分配空间
// 对w和v分配n+1⼤⼩
w = new int[n + 1];
v = new int[n + 1];
// 对T分配n+1⾏，并初始化为0
T = new int *[n + 1]();
// 对T分配W+1列，并初始化为0
for (auto i = 0; i <= n; i++)
{
T[i] = new int[W + 1]();
}
// 输⼊背包的重量和价值
for (auto i = 1; i <= n; i++)
{
cout << "请输⼊第 " << i << " 个物品的重量和价值（⽤空格隔开）" << endl;  cin >> w[i] >> v[i];
if (cin.fail() || w[i] < 0 || v[i] < 0)
{
cout << "输⼊错误！" << endl;
system("pause");
return 0;
}
}
cout << "------------------------------------------------" << endl;
cout << "请选择算法：" << endl;
cout << "【1】迭代法" << endl;
cout << "【2】递归法" << endl;
cout << "------------------------------------------------" << endl;
int choose;
// 输⼊算法的选择
cin >> choose;
编程递归函数
switch (choose)
{
case 1:
{
// 迭代法，能显⽰背包问题的表格
cout << "能装下物品的最⼤价值为 " << packIterative(n, W, w, v) << endl;  cout << "------------------------------------------------" << endl;
printT(n, W);
break;
}
}
case 2:
{
// 递归法，不⽀持显⽰背包问题的表格
cout << "能装下物品的最⼤价值为 " << packRecursive(n, W, w, v) << endl;
break;
}
default:
{
cout << "输⼊错误！" << endl;
break;
}
}
cout << "------------------------------------------------" << endl;
delete w;
delete v;
for (int i = 0; i <= n; ++i) {
delete[] T[i];
}
delete[] T;
system("pause");
return 0;
}
今天的分享就到这⾥了，⼤家要好好学C++哟~
写在最后：对于准备学习C/C++编程的⼩伙伴，如果你想更好的提升你的编程核⼼能⼒（内功）不妨从现在开始！C语⾔C++编程学习交流圈⼦，QQ：904329806【】：C语⾔编程学习基地
整理分享（多年学习的源码、项⽬实战视频、项⽬笔记，基础⼊门教程）
欢迎转⾏和学习编程的伙伴，利⽤更多的资料学习成长⽐⾃⼰琢磨更快哦！
编程学习视频分享：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。