01背包（动态规划，贪心算法，回溯法，分支限界法）_01背包问题贪心算法
赞
踩
1.题目
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
2.例子
number＝4，capacity＝8
| 物品编号（i） | W（体积） | V（价值） |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 6 |
3.实现
1.动态规划
1.什么是动态规划
1.动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，
使得问题能够以递推（或者说分治）的方式去解决。
2.动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），
按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，
丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
2.对题目分析
1.分析
面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。
解决办法：声明一个 大小为 m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，
（1）. j < weight[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
m[ i ][ j ] = m[ i-1 ][ j ]
（2）. j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
如果拿取，m[ i ][ j ]=m[ i-1 ][ j-weight[ i ] ] + value[ i ]。 这里的m[ i-1 ][ j-weight[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。
如果不拿，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）
究竟是拿还是不拿，自然是比较这两种情况那种价值最大。
2.状态转换方程
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-weight[i]]+value[i]);
else
m[i][j]=m[i-1][j];
- 1
- 2
- 3
- 4
3.状态转换图
1）如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
2) 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
3) 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：
3.代码
#define N 100 #include<iostream> #include<algorithm> #include<cstdio> using namespace std; void Knap(int value[], int weight[], int c, int n, int m[][N]) { for (int i = 1; i <= n; i++)//物品i { for (int j = 1; j <= c; j++)//重量j { if (j >= weight[i]) { m[i][j] = max(m[i - 1][j], m[i - 1][j - weight[i]] + value[i]); } else m[i][j] = m[i - 1][j]; } } //for (int i = 0; i <= n; i++)//物品i //{ // for (int j = 0; j <= c; j++)//重量j // { // cout << m[i][j] << ' '; // } // cout << endl; //} } void Trace(int m[][N], int weight[], int c, int n, int x[]) { int h = n, g = c; while (h >= 1) { if (m[h][g] == m[h - 1][g]) x[h] = 0; else { x[h] = 1; g = g - weight[h]; } h--; } } int main() { int value[100]; int weight[100]; int m[N][N] = { 0 }; int x[N]; int c; int n; value[0] = 0; weight[0] = 0; cout << "请输入背包可以承受的重量:"; cin >> c; cout << "请输入物体数量:"; cin >> n; for (int i = 1; i <= n; i++) { printf("请输入第%d个物体的质量与价值:", i); cin >> weight[i] >> value[i]; } Knap(value, weight, c, n, m); Trace(m, weight, c, n, x); for (int i = 1; i <= n; i++) cout << x[i] << " "; cout << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
4.结果
2.贪心算法
1.什么是贪心算法
1.贪心算法的基本思想是找出整体当中每个小的局部的最优解，
并且将所有的这些局部最优解合起来形成整体上的一个最优解。
2.使用贪心算法的问题必须满足下面的两个性质：
1）整体的最优解可以通过局部的最优解来求出；
2）一个整体能够被分为多个局部，并且这些局部都能够求出最优解。
使用贪心算法当中的两个典型问题是活动安排问题和背包问题。
3.贪心算法一般按如下步骤进行:
1）建立数学模型来描述问题。
2）把求解的问题分成若干个子问题。
3）对每个子问题求解，得到子问题的局部最优解。
4）把子问题的解局部最优解合成原来解问题的一个解。
2.对题目分析
1.分析
首先我们按照物品的单位重量价值来进行排序，
然后按照单位重量价值从高到低依次进行选择，
若其能装入背包则将其装入，
不能则继续判断下一个直至所有物品都判断完，
就得到了问题的一个解。
2.缺点
但是对于0-1背包问题，用贪心算法并不能保证最终可以将背包装满，部分剩余的空间使得单位重量背包空间的价值降低了，这也是用贪心算法一般无法求得0-1背包最优解的原因。
3.代码
#include <iostream> #include<algorithm> using namespace std; struct node { double v;//价值 double w;//重量 } wu[100]; bool cmp1(node a, node b)//重量 { if (a.w == b.w) return a.v > b.v; return a.w < b.w; } bool cmp2(node a, node b)//价值 { if (a.v == b.v) return a.w < b.w; return a.v > b.v; } bool cmp3(node a, node b)// 单位价值 { if ((a.v / a.w) == (b.v / b.w)) return a.w < b.w; return (a.v / a.w) > (b.v / b.w); } int fun1(int n, int c) { sort(wu, wu + n, cmp1); int value = 0; for (int i = 0; i < n; i++) { if (c >= wu[i].w) { c -= wu[i].w; value += wu[i].v; } } return value; } int fun2(int n, int c) { sort(wu, wu + n, cmp2); int value = 0; for (int i = 0; i < n; i++) { if (c >= wu[i].w) { c -= wu[i].w; value += wu[i].v; } } return value; } int fun3(int n, int c) { sort(wu, wu + n, cmp3); int value = 0; for (int i = 0; i < n; i++) { if (c >= wu[i].w) { c -= wu[i].w; value += wu[i].v; } } return value; } int random(int n, int c) { int ans = -1, m = 1000; int flag, b[110]; while (m--) { int flag2 = 0, value = 0; for (int i = 0; i < n; i++) { b[i] = 1; } while (1) { flag = rand() % n; if (b[flag] != 0) { if (flag2 + wu[flag].w <= c) { flag2 += wu[flag].w; b[flag] = 0; value += wu[flag].v; } } else { break; } } if (value > ans) { ans = value; } } return ans; } int main() { int n, c;//n个物品，c的容量 cin >> n >> c; for (int i = 0; i < n; i++) cin >> wu[i].w; for (int j = 0; j < n; j++) cin >> wu[j].v; cout << "优先放重量最小的答案："; cout << fun1(n, c) << endl; cout << "优先放价值最大的答案："; cout << fun2(n, c) << endl; cout << "先放性价比最大的答案："; cout << fun3(n, c) << endl; cout << "随机1000次最大的答案："; cout << random(n, c) << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
4.结果
3.回溯法
1.什么是回溯法
1.回溯法概念：
回溯算法有“通用的解题法”之称。用它可以系统地搜索一个问题的所在解或任一解。
回溯法是一个即带有系统性又带有跳跃性的所搜算法。
2.回溯法思想：
1）在包含问题的所有解的解空间树中，按照深度优先搜索的策略，
从根结点出发深度探索解空间树。当探索到某一结点时，
要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，
如果该结点不包含问题的解，则逐层向其祖先结点回溯。
2）若用回溯法求问题的所有解时，要回溯到根，
且根结点的所有可行的子树都要已被搜索遍才结束；
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
3）回溯法解题步骤：
1>针对所给问题，定义问题的解空间
2>确定易于搜索的解空间结构
3>以深度优先方式所搜解空间，并在搜索过程中用剪枝函数避免无效搜索。
2.对题目分析
1.分析
01背包属于找最优解问题，用回溯法需要构造解的子集树。对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，
这样就形成了一棵解空间树： 基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。
在搜索状态空间树时，只要左子节点是可一个可行结点，搜索就进入其左子树。对于右子树时，先计算上界函数，以判断是否将其减去（剪枝）。
上界函数bound():当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。
为了更好地计算和运用上界函数剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
2.设计
利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi （即对n个物品放或不放的一种的方案）
其中， (ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包）。
在递归函数Backtrack中，
当i>n时，算法搜索至叶子结点，得到一个新的物品装包方案。此时算法适时更新当前的最优价值
当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的物品，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
3.解空间树图
4.时间复杂度与空间复杂度
因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为。
因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。
3.代码
#include <iostream> #include <stdio.h> //#include <conio.h> using namespace std; int n;//物品数量 double c;//背包容量 double v[100];//各个物品的价值 double w[100];//各个物品的重量 double cw = 0.0;//当前背包重量 double cp = 0.0;//当前背包中物品总价值 double bestp = 0.0;//当前最优价值 double perp[100];//单位物品价值(排序后) int order[100];//物品编号 //按单位价值排序 void knapsack() { int i, j; int temporder = 0; double temp = 0.0; for (i = 1; i <= n; i++) perp[i] = v[i] / w[i]; //计算单位价值（单位重量的物品价值） for (i = 1; i <= n - 1; i++) { for (j = i + 1; j <= n; j++) if (perp[i] < perp[j])//冒泡排序perp[],order[],sortv[],sortw[] { temp = perp[i]; //冒泡对perp[]排序 perp[i] = perp[j];//单位物品价值 perp[j] = temp; temporder = order[i];//冒泡对order[]排序 order[i] = order[j];;//物品编号 order[j] = temporder; temp = v[i];//冒泡对v[]排序 v[i] = v[j];//各个物品的价值 v[j] = temp; temp = w[i];//冒泡对w[]排序 w[i] = w[j];//各个物品的重量 w[j] = temp; } } } //计算上界函数，功能为剪枝 double bound(int i) { //判断当前背包的总价值cp＋剩余容量可容纳的最大价值<=当前最优价值 double leftw = c - cw;//剩余背包容量 double b = cp;//记录当前背包的总价值cp,最后求上界 //以物品单位重量价值递减次序装入物品 while (i <= n && w[i] <= leftw) { leftw -= w[i]; b += v[i]; i++; } //装满背包 if (i <= n) b += v[i] / w[i] * leftw; return b;//返回计算出的上界 } //回溯函数 void backtrack(int i) { //i用来指示到达的层数（第几步，从0开始），同时也指示当前选择玩了几个物品 if (i > n) //递归结束的判定条件 { bestp = cp; return; } //如若左子节点可行，则直接搜索左子树; //对于右子树，先计算上界函数，以判断是否将其减去 if (cw + w[i] <= c)//将物品i放入背包,搜索左子树 { cw += w[i];//同步更新当前背包的重量 cp += v[i];//同步更新当前背包的总价值 backtrack(i + 1);//深度搜索进入下一层 cw -= w[i];//回溯复原 cp -= v[i];//回溯复原 } if (bound(i + 1) > bestp)//如若符合条件则搜索右子树 { backtrack(i + 1); //后续节点的价值上界大于当前最优价值，则可以进入右界面 否则最优的都小于或等于当前的 就没必要再进入右节点 //进入右节点 因为不加入到背包 故 当前的价值 重量 都不发生改变 } } int main() { int i; printf("请输入物品的数量和背包的容量："); scanf_s("%d %lf", &n, &c); printf("请依次输入%d个物品的重量:\n", n); for (i = 1; i <= n; i++) { scanf_s("%lf", &w[i]); order[i] = i; } printf("请依次输入%d个物品的价值:\n", n); for (i = 1; i <= n; i++) { scanf_s("%lf", &v[i]); } knapsack(); backtrack(1); cout << endl; printf("最优价值为：%.lf\n", bestp); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
4.结果
4.分支限界法
1.什么是分支限界法
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，
其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
2.对题目分析
1.分析
函数MaxKnapSack使用分支限界法
用子集树表示，左子节点表示当前物品放入，右子节点表示当前物品不放入。
优先级：按照优先队列中节点元素N的优先级由上界函数bound计算出的uprofit给出。（就是当前背包的重量+剩余可以放的重量）（剩余的物品按照单位重量价值非升序排序，将单位重量价值大的先放 入，放不下整个物品的话，就放入一部分。）如果到达了叶节点，由于使用的是优先队列，所有活结点价值上届不超过该叶节点价值，是最优值
2.时间复杂度与空间复杂度
空间：最坏情况下需搜索2^(n +１) –２个节点，需O(2^n ) 个空间存储节点，则算法空间复杂性为O(2^n ）
时间：最坏情况有 2^(n +１) - ２ 个节点，限界函数时间复杂度O（n），若 对每个节点用限界函数判断，则其时间复杂度为O(n2^n).
3.代码方法1
#include <iostream> #include<cstdio> #include<queue> using namespace std; const int N = 110; struct stone { int v, w; stone() { v = w = 0; } bool operator < (stone b) const { return v / w > b.v / b.w; } }item[N]; struct node { int level, cv, cw; float bound; bool operator< (const node& b) const { return bound > b.bound; } }; int best, W, n; inline void Initialize(priority_queue<node>& Q) { while (Q.size()) Q.pop(); } float bound(node& p) { int left = W - p.cw; float val = p.cv; int i; for (i = p.level; i <= n && item[i].w <= left; i++) { left -= item[i].w; val += item[i].v; } if (i <= n) val += item[i].v * 1.0 / item[i].w * left; return val; } priority_queue<node> PQ; void knapsack() { node u, v; Initialize(PQ); v = { 0,0,0,0 }; best = 0; v.bound = bound(v); PQ.push(v); while (PQ.size()) { v = PQ.top(); PQ.pop(); if (v.level == n) continue; if (v.bound > best) { u.level = v.level + 1; u.cw = v.cw + item[u.level].w; u.cv = v.cv + item[u.level].v; //printf("%d %d\n", u.cw, u.cv); if (u.cw <= W && u.cv > best) best = u.cv; u.bound = bound(u); if (u.bound > best) PQ.push(u); u.cw = v.cw; u.cv = v.cv; u.level = v.level + 1; u.bound = bound(u); if (u.bound > best) PQ.push(u); } } } int main() { printf("请输入物品的数量和背包的容量："); scanf_s("%d %d", &n, &W); printf("请依次输入%d个物品的重量:\n", n); for (int i = 1; i <= n; i++) { scanf_s("%d", &item[i].w); } printf("请依次输入%d个物品的价值:\n", n); for (int i = 1; i <= n; i++) { scanf_s("%d", &item[i].v); } sort(item + 1, item + 1 + n); knapsack(); printf("%d\n", best); return 0; } /* 4 7 3 5 2 1 9 10 7 4 20 */
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
4.结果1
5.代码方法2
#include <iostream> #include<cstdio> #include<queue> using namespace std; //分支限界发求解01背包问题 基于的是贪心思想 在第1个物品放入 和没放入背包时 其实 都有一个理论上可能达到的最大价值 //我们选理论价值最大的那个可能性 如果该物品放入背包 可能的价值大 我们就走这条路 如果这个不放入 价值大 我们就走另外一条路 //总容量 int totalvolume; //物品数量 int amount; //递增系数 int id_add = 0; //定义一个结构 struct element { //编号 int Id; //重量 int Weight; // 价值 int Worth; element() { Id = id_add++; Weight = 0; Worth = 0; } }; //保存某个方案 struct PLAN { //每个方案都会保存一个数组 （每个物品 是否放入） bool isIn[11] = { 0 }; // 已经存入的物品的价值 double alreadyWorth; //可能最大利益 double mostWorth; //剩余容量 int leftVolume; //第Id个物品是否放入 这表示前Id-1个物品 是否放入都已经确定了 int Id; PLAN() { } //初始化 所有物品都没放入的初始状态 void Init(element* Array) { alreadyWorth = 0; mostWorth = 0; leftVolume = totalvolume; Id = 0; calculate(Array); }; //后序所有的初始化都采用这个 都是在前面基础上 判断第n个物品是否放入 放入是1 不放入是0 void Init(PLAN& a, int is_in, element* Array) { std::copy(a.isIn, a.isIn + amount, isIn); //不放入 Id = a.Id; leftVolume = a.leftVolume; alreadyWorth = a.alreadyWorth; //放入 if (is_in == 1 && leftVolume - Array[Id].Weight >= 0) { leftVolume -= Array[Id].Weight; alreadyWorth += Array[Id].Worth; isIn[Id] = 1; } Id++; calculate(Array); }; //计算某个方案的 mostWorth void calculate(element* Array) { int id_used = Id; int leftVolume1 = leftVolume; mostWorth = alreadyWorth; while (id_used <= amount - 1 && leftVolume1 - Array[id_used].Weight >= 0) { leftVolume1 -= Array[id_used].Weight; mostWorth += Array[id_used].Worth; id_used++; } if (leftVolume1 > 0 && id_used <= amount - 1) { mostWorth += leftVolume1 * ((double)Array[id_used].Worth / (double)Array[id_used].Weight); } } }; bool operator<(const PLAN& a, const PLAN& b) { return a.mostWorth < b.mostWorth; } bool operator>(const PLAN& a, const PLAN& b) { return a.mostWorth > b.mostWorth; } bool operator>=(const PLAN& a, const PLAN& b) { return a.mostWorth >= b.mostWorth; } ostream& operator<<(ostream& os, const PLAN& a) { for (int i = 0; i <= 10; i++) { if (a.isIn[i] == 1) { os << i + 1 << " "; } } os << "最优方案价值为" << a.alreadyWorth << endl; return os; } bool cmp_element(element& a, element& b) { return ((double)a.Worth / a.Weight) > ((double)b.Worth / b.Weight); } int main() { srand((unsigned)time(NULL)); //大根堆 priority_queue<PLAN>mHeap; cout << "请输入总的容量" << endl; cin >> totalvolume; cout << "输入物品数量" << endl; cin >> amount; element* Item = new element[amount]; for (int i = 0; i < amount; i++) { cout << "输入第" << i + 1 << "组物品的重量和价值。以空格隔开" << endl; cin >> Item[i].Weight >> Item[i].Worth; } //按性价比排序 std::sort(Item, Item + amount, cmp_element); cout << " 排序之后：" << endl; for (int i = 0; i < amount; i++) { cout << i + 1 << " " << Item[i].Weight << " " << Item[i].Worth << endl; } //临时方案 PLAN tempPlan; tempPlan.Init(Item); //临时方案 PLAN tempPlan1; while (tempPlan.Id != amount) { //第n个物品放入 tempPlan1.Init(tempPlan, 0, Item); mHeap.push(tempPlan1); //第n个物品不放入 tempPlan1.Init(tempPlan, 1, Item); mHeap.push(tempPlan1); tempPlan = mHeap.top(); mHeap.pop(); } //循环结束的方案 即为最优方案 因为到达叶子节点 cout << tempPlan; system("pause"); delete[]Item; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
6.结果2
