❶ 分支定界法 0-1多背包问题
的动态规划0-1背包问题
/ ************************************* *********************************** /
/ * 0-1背包问题： /> / * n种物品和一个背包
/ *项目无线网络，我的体重VI的价值
/ *背包的容量为c
/ *应该如何选择项目加载背包使物品装入背包
/ *总最看重的吗？
/ *注：选择项目装入背包的物品我只有两个选择
/ *加载或不装入背包。我不能加载多个
/ *不能只是加载的项目。
/ *
/ * 1。 0-1背包问题的形式化描述：
/ * C> 0，无线网络> 0，六0，0 <= I <= N要求找到一个n
/ * 0-1向量（ X1，X2，...，XN），使得：
/ *最大sum_ {= 1到n}（ⅵ*ⅹⅰ），并满足下面的约束：
/ *（1）sum_ {I = 1到n}（WI *十一）<= C
/ *（2）十一∈{0，1} 1 <= I <= N
/ * ...... / a>
/ * 2。
/ * 0-1背包问题0-1背包问题的解决有重叠的性质的最优子结构性质和子适合
/ *使用动态规划方法解决
/
/ * 2.1最优子结构性质
/ *设置（Y1，Y2，...，yn）的0-1背包问题，最佳的解决方案，它肯定
> / *结论（Y2，Y3，...，yn）的是下面的子问题的最优解：
/ *最大sum_ {i = 2到n}（VI *十一）
/ *（1）sum_ {i = 2到N}（WI *十一）<= C - W1 * Y1
/ *（2）十一∈{0，1}，2 <= I <= N /> / *否则，子问题有一个最优的解决方案（Z2，Z3，...，zn的），
/ *（Y2，Y3，...，yn）的比的最优解。然后：
/ * sum_ {i = 2到n}（VI *子）sum_ {i = 2到n}（VI *易）
/ *，W1 * Y1 + sum_ {i = 2到n}（WI *子）<= C
/ *进一步指出：
/ * V1 * Y1 + sum_ {i = 2到n}（VI *子）> sum_ {i = 1 N}（VI *易）
/ * W1 * Y1 + sum_ {i = 2到n}（无线ZI）<= C
/ *这说明：（Y1，Z2，Z3， ，...，ZN）0-1背包问题是一个更好的解决方案，然后
/ *说明（Y1，Y2，...，yn）的是不矛盾的前提下，最佳的解决方案，因此，最好
/ *建立的子结构的性质。
/ *
/ * 2.2子重叠性质
/ *设置给定的0-1背包问题的子P（I，J）：
/ *最大sum_ {K = I N}（VK * XK）
/ *（1）sum_ {K = I为n}（周* XK）<= J
/ *（2）XK∈{0，1}， I <= K <= N
/ * P（I，J）的问题是背包容量为j，可选的项目我，我+1，...，n的子的问题
/ *设M（I，J）是子P（I，J），最大总价值的最优值。在最佳
/ *子结构的性质可以创建递归米的（I，J）：
/ *。递归的初始M（N，J）
/ * / /背包容量为j，可选的项目只有n，，如果背包容量j是大于项目?
/ / /重量直接加载;无法加载。
/ * M（N，J）= VN，J> = WN
/ * M（N，J）= 0，0 <= J <WN
/ * B。递推公式M（I，J）
/ * / /背包容量?，可选的项目我，我+1，...，N
/ * / /背包容量J <无线网络，后来干脆不安装成的文章：
/ * M（I，J）= M（I +1，J），0 <= j的无线
/ * / / J> =无线网络，文章中，我加载的项目之间我选择
/ *没有我的最佳值：M（i +1，j）的安装项目
/ *加载项，我的最优值：M（i +1， J-WI）+ VI
/ *：
/ * M（I，J）= {M（I +1，J），M（I +1，J-无线）+ VI}，J> =无线
/ *
/ ***************************** ******************************************* /
/>
定义MAX（A，B）（（（一）（二））（A）（B））
定义分（A，B）（ （（A）（B））（A）（B））
模板
无效背包（类型* V，INT * W，C，N，类型* * M）
{
/ /递归的初始条件
诠释JMAX = MIN（W [N] - 1，C）;
（J = 0;? <= JMAX J + +）{
米[N] [J] = 0;
}
（J = W [N]; <= C; J + +）{
M [N] [J] = V [N];
}
/ /我从2到n-1，分别为j> = wi和0 <= j的无线M（I，J）
（INT I = N-1; i> 1的，我 - ）{
JMAX = MIN（W [我] - 1，C）;
（J = 0; <= JMAX; J + +）{
M [] [J] = M [+1] [J]; ...... />}
为（J = W [I]; <= C; + +）{
M [] [J] = MAX（M [+1] [J]， M [+1] [JW [我] + V [I]）;
}
}
M [1] [C] = M [2] [ C];
（C> = W [1]）{
M [1] [C] = MAX（M [1] [C]，M [2] [CW [1]] + V [1]）;
}
}
模板
无效回溯（类型**米，INT * W， INT整数N，C，* X）
{
为（int i = 1; <N，我+ +）{
（M [] [C] == M [+1] [C]）×[I] = 0;
其他{
×[我] = 1;
C - = W [I];
}
}
×[N] =（M [N] [C]）？ 1:0;
}
：（INT ARGC，字符*的argv []）
{
廉政n = 5;
>诠释W [6] = {-1，2，2，6，5，4};
INT V [6] = {-1，6，3，5，4，6};
>诠释C = 10;
** ppm =百新诠释[N +1];
（INT I = 0; I <N +1，我+ +）{
PPM [] =新的int [C +1];
}
诠释x [6];
背包的（V ，W，C，N，PPM）;
：回溯的（ppm时，W，C，N，X）;
返回0;}
贪心算法求解0-1背包问题
的基本思路？贪婪的方法：
逐渐接近目标，给予尽可能快地获得一个更好的解决方案在地上 - 从最初的解决方案的问题。当达到一个算法的步骤不能继续向前走，算法停止。
的算法问题：
1）不能保证获得最终的解决方案;
2）不能被用来谋求最大或最小解决方案;
3）寻求满足一定的约束条件，可行的解决方案。
算法：
开始从最初的解决方案的问题;
获得可行的解决方案提出了总体目标，而移动元素的解决方案;
所有解决方案组件组合成一个可行的解决方案的问题;
2实例分析
1）。背包问题，背包，背包容量是M = 150。 7物品时，物品可分为任意的尺寸。的
要求尽可能多，以使总价值的物品装入背包，但不能超过总容量。
的项ABCDEFG
权重值35 30 60 50 40 10 25
10 40 30 50 35 40 30
：
目标函数： σpi，
约束装入的物品的总重量计不超过背包容量：Σwi<= M（M = 150）
（1）根据贪心策略，每个选定的值最大的装载物品的背包，得到的结果是最优的？
（2）每次选择负载最小的项目可以得到最佳的解决方案吗？
（3）每次你选择一个单位容量的最有价值的项目，解决这个问题的战略。
（环境：C + +）
包括与ltiostream.h的>
＃定义最大100 / /最大数量的项目
无效排序（N，飘起了[MAX]，持股量B [MAX]）/ /密度值的排序
{
整数J，H，和K;
持股量T1，T2， T3，C [MAX];
（k = 1时，K <= N，K + +）
?[K] = [K] / B [K]
（H = 1，H <N，H + +）
（J = 1，J <= NH J + +）
（C [J] C [j +1]中）
{T1 = A [J]，A [J] = A [j +1]中的[J +1] = T1;
T2 = B [J]; B [J] = B [j +1]中，B [J +1] = T2;
T3 = C [J] C [J] = C [j +1]中，C [J +1] = T3;
>}
}
无效背包（INT N，持股量limitw，浮动V [MAX]，浮瓦特[MAX]，诠释x [MAX]）
{浮动C1 / / C1背包剩余的负载重量
我
排序（N，V，W）/ /排序价值密度的
C1 = limitw
为（i = 1我=我+ +）
{
（W [I]> C1）打破;
×[我] = 1; / / x [我]的文章我了解
C1 = C1-W [I];
}
}
无效的主要（）
{N，I，X [MAX];
>浮法V [MAX]，W [MAX]，totalv = 0，totalw = 0，limitw;
法院<<“请输入n和limitw：”
CIN >> N >> limitw
为（i = 1; <=我+ +）
×[我] = 0; / /初始化为0的产品选择表
法院<<“请进入价值的项目依次：“<< endl;
（i = 1; <=我+ +）
CIN >> V [I];
法院<; <endl;
法院<<“请输入的重量反过来的项目：”<< endl;
（i = 1; <= N; + +）
CIN >> W [I];
法院<< endl;
背包（N，limitw，V，W，X）;
法院<<“选择的是：”
>（i = 1; <= N; + +）
{
法院<< X [I];
（X [I] == 1） totalw = totalw + W [I];
}
法院<< endl;
法院<<“总重量的背包：<<totalw << endl; / /背包装载总重量
法院<<“总价值的背包为：的”“totalv << endl; / /背包的总价值
}
三回溯算法0 -1背包问题
1.0-l背包问题是选定的子集的问题。
一般,0-1背包问题是NP-难的。
0-1背包解决方案的可用空间的一个子集树。
喜欢回溯0-1背包问题装载问题的回溯是非常一流。搜索解空间树的搜索，只要其左子节点是一个可行的节点，进入其左子树。
右子树可能只包含右子树搜索的最佳解决方案，否则，切右子树。设r其余
商品的价值的总和;阴极保护电流值;当前最优值bestp。
子树可以削权当CP + R≤bestp。在右子树的上限解的计算是更好的方法，其余项目根据其单位重量排序的值
然后在打开加载项直到合适的，然后到的文章充满背包。得到的值是上限
右子树的解决方案。
2。解决方案的想法：
为了便于计算中上的第一个项目，每单位重量的约束根据降序自己的价值，并此后，只要测试的顺序
可以观察到的各种物品。在实现绑定在当前节点的上限计算。搜索解决方案空间树，只要其左子节点是一个可行的节点，搜索到的左子树，右子树可能含有进入右子树搜索的最佳解决方案之前，否则，切右子树。
回溯跳跃系统的搜索算法。它包含了所有问题的解空间树的解决方案，根据深度优先的策略，开始从根本上搜索解空间树。总是首先确定节点的解决方案不包含树算法搜索的解空间中的任何节点。当然不包含跳层和它的祖先节点的节点是根的子树的搜索回溯系统，否则，进入子树，继续深入搜索优先策略。回溯所有使用的解决方案，提出了一个问题，我们必须回头去根，根的子树搜索，直到结束。回溯，用乞求的问题，任何一个解决方案，只要搜索一个解决问题的办法可以结束了。被称为回溯的深度优先搜索算法的问题的解决方案，它适用于了解一些大量的组合。
2。算法框架： BR />问题的解空间：应用回溯法解决问题，首先应该明确的定义问题的解决空间问题的解空间中至少包含一个（最佳）的解决方案。
B。回溯基本思想是：以确定的组织结构对空间的理解，回溯从开始节点（根），深度优先搜索整个解空间的起始节点成为一个活结点，也是当前扩展节点。在当前的扩展结中，搜索到的深度方向移动到一个新的节点。新的节点是一个新的活结点，和目前的扩张节点，如果当前的交界处延长不能进一步移动，在深度方向上，那么当前的扩展结点死锁。换言之，此节点不再是一个活结点，在这一点上，应该向后移动（回溯）指向一个活结活结扩展节点停止回溯这样的递归地搜索解空间中工作，直到你找到解决方案或解决方案所需的空间活结点。
3。用回溯法解决问题通常是由以下三个步骤：
解决方案的空间一个给定的问题，定义问题;
B。确定易于搜索的解空间结构;
C。深度优先的方式搜索解空间，并在搜索过程中通过修剪功能，以避免无效搜索;
＃包括
使用命名空间std;
类雷德克纳普
{
朋友整数背包（P []，诠释W []，诠释三，廉政n）;
：
无效的print（）
{
（M = 1，M <= N，M + +）
{
法院<< bestx [M] <<“”;
}
法院<< endl;
};
私人如下：
整数约束（int i）的;
无效回溯（int i）的;
诠释三;/ /背包容量
廉政n，/ /项目数
诠释* W / /菜单项权重数组
诠释* p ;/ /项目值的数组
诠释CW ;/ /重量
INT CP ;/ /电流值
诠释bestp ;/ /当前的最优值
诠释* bestx ;/ /当前最优解
诠释*
}
诠释雷德克纳普::绑定（一）
{
/ /计算x ;/ /当前的解决方案上限
诠释裂= C-CW ;/ /剩余容量
INT B = CP;
/ /项目单位重量价值递减的序列加载项
（I <= N &&瓦特[I] <=裂）
{
裂= W [I]
B + = [];
+ +;
>}
/ /填充背包
如果（i <= N）
B + = [I] / W [I] *裂;
回报B; ...... />}
无效雷德克纳普::回溯（一）
{
如果（I>）
{
（ bestp <CP）
{
（J = 1; <= N; + +）
bestx [J] = [J]。
bestp = CP
}
回报;
}
（CW + W [I] <= C）/ /搜索左子树
{
×[我] = 1;
CW + = W [I];
CP + = [];
回溯 - 触控板（i +1）;
CW - = W [I];
CP-= P [I];
}
如果“（绑定（i +1）> bestp）/ /搜索右子树
{ BR /> x [I] = 0;
回溯 - 触控板（i +1）;
}
}
>类对象
{
朋友整数背包（P []，诠释W []，诠释三，廉政n）;
内部操作符<=（对象A ）常量
{
回报率（D> =广告）;
}
私人如下：
整数ID;
浮动D; />};
整数背包（P []，诠释W []，诠释三，廉政n）
{
/ /为雷德克纳普： ：Backtrack面板 - 触控板初始化
诠释W = 0;
诠释P = 0;
INT I = 1;
对象* Q =新的对象[N]; / a>（I = 1; <=我+ +）
{
Q [I-1]。ID =我;
Q [I-1]，D = 1.0 * P [I] / W [I];
P + = [];
W + = W [I];
}
（W <= C）
回报P ;/ /加载的所有项目
/ /按产品单位重量排序
浮F;
为（i = 0; I <N;我+ +）
（整数J = I，J <N; J + +）
{
（Q [I]，D <Q [J]。四）
{ BR /> F = Q [I]，D;
Q [我]，D = Q [J]。天;
Q [J]。D = F;
}
a>
}
雷德克纳普K;
KP =新的int [N +1];
KW =新的int [N +1];
KX = INT [N +1];
K.bestx =新的int [N +1];
KX [0] = 0;
K.bestx [0 ] = 0;
为（i = 1; <= N; + +）
{
KP [I] = P [Q [I-1]。ID]; BR /> KW [我] = W [Q [I-1]。ID];
}
K.cp = 0;
K.cw = 0;
KC = C;
KN = N;
K.bestp = 0;
/ /回溯搜索
K.Backtrack（）;
K.print的（）
删除[] Q;
删除[]千瓦;
删除[] KP;
回报K.bestp;
}
无效的主要（）
{
* P;
* W;
整数C = 0;
廉政n = 0;
> INT I = 0;
字符K表;
法院<<“0-1背包问题 - 回溯”<< endl;
法院<<“通过zbqplayer <而（K）
{
法院<<“请输入一个背包容量（C）：”<< endl;
CIN >> C;
法院<<“请输入的项目数（n）：“<< endl;
CIN >> N
P =新的int [N +1];
W =新的int [ +1];
P [0] = 0;
W [0] = 0;
法院<<“请输入一个值（P）的项目： << endl;
（i = 1; <= N; + +）
CIN >> P [I];
法院<<“请输入项目的重量（W）：“<< endl;
为（i = 1; <=我+ +）
CIN >> W [I]
BR />法院<<“最佳的解决方案（bestx）：”<< endl;
法院<<“最佳的值（bestp）：”<< endl;
的cout <<背负的（P， W，C，N）<< endl;
法院<<“[S]重新启动”<< endl;
法院<<“[q]退出”<< endl; BR /> CIN >> K
}
四个分支定界法求解0-1背包问题
问题描述：已知的N项和一个背包可以容纳M个权重，权重我的体重，只认沽或不投入，解决如何把在背包中的物品的总收益的项目，可以使每一个项目。
2。设计的思考和分析：选择的项目，或不构成解决方案树，左子树不加载，正确的说，节点负载，以获得最佳的树检索问题的解决办法谢界杀不符合要求的节点。
包括
结构良好
{
诠释权重;
诠释的利益;
INT标志;/ /是否加载标签
};
整型数= 0 ;/ /项目数
诠释upbound = 0;
诠释curp = 0，curw = 0 ;/ /当前实际价值和重量
诠释maxweight = 0;
好包= NULL;
的虚空Init_good（）{
>袋=新好[数字];
（INT I = 0;我数，我+ +）
{
法院<<“请输入第一块“。 ;“<< i +1 <<”重的项目：“
CIN >>袋[i]的重量;
法院<<”请输入片“<< i +1 << “项目的好处：”
CIN >>袋[I]。利益;
袋[I]。标志= 0 ;/ /初始标志没有被装入背包
法院<< endl;
}
}
诠释getbound（整数民， * bound_u）/ /返回节点c计和压力表ü
{
（瓦特= curw，P = curp，民数&&（W +包[NUM]重量）<= maxweight NUM + +）
{
W = W +包[NUM]。重量;
P = W +包[NUM]。效益;
}
* bound_u = P +包[NUM]。 ，效益;
回报（P +包[NUM]。利益（（maxweight-W）/袋[NUM]。重量））;
}
无效LCbag（）
{
bound_u = 0，bound_c = 0 ;/ /当前节点c方向和u和约束
（i = 0;号码;我+ +层）/ /层穿越解决方案，树，以决定是否加载不同的项目
{（I +1，及bound_u））>
（（bound_c =的getbound upbound）/ /遍历左子树
upbound = bound_u ;/ /改变有U计不会改变的标志
如果“（getbound（I＆bound_u）> bound_c）/ /遍历右子树
/ /如果加载，以确定是否大于左子树的根的右子树C标尺C标尺负载
{的
upbound = bound_u ;/ /变化有u和约束
curp = curp +包[I]。利益的
curw = curw +包[i]的重量;/ /重量和效益从现有再加上新的项目
袋[I]。标志= 1; / /标记加载
}
}
}
显示（）
{
/> COUT <<“项目可放置在背包里数：”;
（INT I = 0;我数，我+ +）
（袋[I]。标志> 0 ）
法院<< i +1 <<“”;
法院<< endl;
删除[]袋;
}
❷ 有关语言的问题
算上n次就行了
❸ 装载问题的贪心选择性质如何证明
设箱子重量从小到大（x1,x2,...,xn），若集合A是最优装载问题的一个最优解。A中第一个箱子为k。若k=1，A就是一个满足贪心性质的最优解。假如当k>1，令B=A-{k}+{1},因为Wk>=W1,则B中的总重量小于等于A中的总重量，A是最优解，则B也是最优解，而B是选择以箱子1为开始的最优解。可知总存在以贪心选择开始的最优解。
❹ 0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）
一.动态规划求解0-1背包问题
/************************************************************************/
/* 0-1背包问题：
/* 给定n种物品和一个背包
/* 物品i的重量为wi，其价值为vi
/* 背包的容量为c
/* 应如何选择装入背包的物品，使得装入背包中的物品
/* 的总价值最大？
/* 注：在选择装入背包的物品时，对物品i只有两种选择，
/* 即装入或不装入背包。不能将物品i装入多次，也
/* 不能只装入部分的物品i。
/*
/* 1. 0-1背包问题的形式化描述：
/* 给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且满足如下约束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包问题的求解
/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于
/* 采用动态规划方法求解
/*
/* 2.1 最优子结构性质
/* 设(y1,y2,...,yn)是给定0-1背包问题的一个最优解，则必有
/* 结论，(y2,y3,...,yn)是如下子问题的一个最优解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因为如若不然，则该子问题存在一个最优解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最优解。那么有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 进一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 这说明：(y1,z2,z3,...zn)是所给0-1背包问题的更优解，那么
/* 说明(y1,y2,...,yn)不是问题的最优解，与前提矛盾，所以最优
/* 子结构性质成立。
/*
/* 2.2 子问题重叠性质
/* 设所给0-1背包问题的子问题 P(i,j)为：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 问题P(i,j)是背包容量为j、可选物品为i,i+1,...,n时的子问题
/* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优
/* 子结构性质，可以建立m(i,j)的递归式：
/* a. 递归初始 m(n,j)
/* //背包容量为j、可选物品只有n，若背包容量j大于物品n的
/* //重量，则直接装入；否则无法装入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量j<wi，则根本装不进物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，则在不装物品i和装入物品i之间做出选择
/* 不装物品i的最优值：m(i+1,j)
/* 装入物品i的最优值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//递归初始条件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i从2到n-1，分别对j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);
return 0;
}
二.贪心算法求解0-1背包问题
1.贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1).不能保证求得的最后解是最佳的；
2).不能用来求最大或最小解问题；
3).只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
2.例题分析
1).[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。
<程序代码:>(环境:c++)
#include<iostream.h>
#define max 100 //最多物品数
void sort (int n,float a[max],float b[max]) //按价值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1为背包剩余可装载重量
int i;
sort(n,v,w); //物品按价值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]为1时，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"请输入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout<<"请依次输入物品的价值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"请依次输入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的总重量为："<<totalw<<endl; //背包所装载总重量
cout<<"背包的总价值为："<<totalv<<endl; //背包的总价值
}
三.回溯算法求解0-1背包问题
1.0-l背包问题是子集选取问题。
一般情况下，0-1背包问题是NP难题。0-1背包
问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类
似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当
右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余
物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右
子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后
依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是
右子树中解的上界。
2.解决办法思路：
为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考
察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
2.算法框架：
a.问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。
b.回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
3.运用回溯法解题通常包含以下三个步骤：
a.针对所给问题，定义问题的解空间；
b.确定易于搜索的解空间结构；
c.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包问题——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"请输入背包容量(c)："<<endl;
cin>>c;
cout<<"请输入物品的个数(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"请输入物品的价值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"请输入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最优解为(bestx)："<<endl;
cout<<"最优值为(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新开始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包问题
1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。
2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
#include <iostream.h>
struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};
int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"请输入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"请输入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界
for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志
if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的编号为：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
❺ C语言关于装载问题（背包问题）的一个程序 我写的程序输出不满足题意 但我检查不出来错误 希望大神解决
想法:是先让c1船尽量装货物是可以的，但是算法应该不对，可以用下面的算法
// 前k个数中去任意个数，且这些数之和为s的取法是否存在
int main()
{
int n, i, k1, k2, s, u;
cin >> n;
for (i=1; i<=2*n; i++)
cin >> A[i];
int sum = 0;
for (i=1; i<=2*n; i++)
sum += A[i];
memset(dp,0,sizeof(dp));
dp[0][0]=true;
// 外阶段k1表示第k1个数，内阶段k2表示选取数的个数
for (k1=1; k1<=2*n; k1++) // 外阶段k1
{
for (k2=k1; k2>=1; k2--) // 内阶段k2
for (s=1; s<=sum/2; s++) // 状态s
{
//dp[k1][s] = dp[k1-1][s];
// 有两个决策包含或不包含元素k1
if (s>=A[k1] && dp[k2-1][s-A[k1]])
dp[k2][s] = true;
}
}
// 之前的dp[k][s]表示从前k个数中取任意k个数，经过下面的步骤后
// 即表示从前k个数中取任意个数
for (k1=2; k1<=2*n; k1++)
for (s=1; s<=sum/2; s++)
if (dp[k1-1][s]) dp[k1][s]=true;
// 确定最接近的给定值sum/2的和
for (s=sum/2; s>=1 && !dp[2*n][s]; s--);
}
❻ 贪心算法的最优装载问题
void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)
1.void loading(int W[],int X[],int c,int n)
2.没有定义i;
3.for（;;）是冒号，非逗号
❼ 最优装载：有一批集装箱要装上一艘载重量为totalW的轮船，其中集装箱i的重量为wi。最有装载问题要求在装在
453453