锐客网

  1. 首页 > it技术 > >

01背包，完全背包C++实现

c++

首先，上自己的代码，由于代码注释详细，我就不解释啦。看代码就好O(∩_∩)O。
代码转换为了01背包问题求解。
代码部分算法与测验数据数据参照了https://blog.csdn.net/xp731574722/article/details/70766804
不了解01背包算法的同学也可以到上述网址先学习。
本代码可以输出价值与背包中的物品。
供大家一起学习使用，如需转载代码请告知本人。
先为大家双手奉上运行结果。
01背包，完全背包C++实现
文章图片

#include #include using namespace std; #define Volumn 14 //背包总容量为Volumn-1 #define N 7 //存在N-1个物品//包裹结构 typedef struct APac { int value; //包裹总价值 int k; //主函数中声明了一个m[i][j]的二维数组，k表示有k个i号物品 int smallPac; //背包总容量减去k*i,即一个没有i的小背包 APac() { value = https://www.it610.com/article/0; k = 0; smallPac = 0; } }APac,*pPac; int main() { int v[N] = { 0,8,10,6,3,7,2 }; //为了方便表示，0号位不使用，1~6表示价值 int w[N] = { 0,4,6,2,2,5,1 }; //同样，表示重量 //声明背包二维数组 APac m[N][Volumn]; for (int i = 0; i < N; i++) { for (int j = 0; j < Volumn; j++) { m[i][j] = *new APac(); } } //采用01背包方法，增加第三重k循环，求最值。 for (int i = 1; i < N; i++) { for (int j = 1; j < Volumn; j++) { //可以拿,判断容量为j的背包，不拿i价值高 还是 (拿i即i的价值加j-w[i]背包的最高价值)高 for (int k = 0; k*w[i] <= j; k++) if (j>= w[i]) { //用于记录背包组成，与输出背包组成有关 if ((m[i - 1][j - k * w[i]].value + k * v[i]) >= m[i][j].value && (m[i - 1][j - k * w[i]].value + k * v[i]) >= m[i - 1][j].value) { m[i][j].k = k; m[i][j].smallPac = j - k * w[i]; } //记录背包价值 m[i][j].value = https://www.it610.com/article/max(m[i][j].value, max(m[i - 1][j].value, m[i - 1][j - k * w[i]].value + k * v[i])); } else { //记录背包组成与价值 m[i][j].k = m[i - 1][j].k; m[i][j].smallPac = m[i - 1][j].smallPac; m[i][j].value = m[i - 1][j].value; } } } //输出背包价值 cout <<"背包价值" << endl; for (int i = 1; i < N; i++) { for (int j = 1; j < Volumn; j++) { cout << m[i][j].value << " "; } cout << endl; } cout << endl; //输出背包组成 cout << "背包组成" << endl; int y = Volumn-1; for (int i = N-1; i > 0; i--) { cout << m[i][y].k<<"个"<

【01背包，完全背包C++实现】

    推荐阅读


    上一篇：详解三次握手和四次挥手

    下一篇：她可能是唯一一个大家都不想要她怀孕的女主角吧