0-1背包问题的多种解法代码(动态规划、贪心法、回溯法、分支定界法)

/************************************************************************/

/* 0-1背包问题:

/*给定n件物品和一个背包

/*项I的重量为wi，其值为vi。

/*背包容量为c。

/*我应该如何选择要放入背包的物品，以便将物品放入背包

/*的总值最大？

/*注意:在选择要装进背包的物品时，物品I只有两个选项。

/*也就是有没有背包。项目I不能多次加载，并且

/*只有部分项目I无法加载。

/*

/* 1的形式描述。0-1背包问题；

/*给定c & gt0，wi & gt0，vi & gt0，0 & lt= i & lt=n，需要找到一个n元

/* 0-1向量(x1，x2，...，xn)，这样:

/* max sum_{i=1到n} (vi*xi)并满足以下约束:

/* (1) sum_{i=1到n }(wi * Xi)& lt；= c

/* (2) xi∈{0，1}，1 & lt；= i & lt=n

/*

/* 2.0-1背包问题求解

/* 0-1背包问题具有最优子结构性质和子问题重叠性质，适用于

/*用动态规划法求解。

/*

/* 2.1最优子结构的性质

/* Let (y1，y2，...，yn)是给定的0-1背包问题的最优解，那么一定有。

/*结论，(y2，y3，...yn)是以下子问题的最优解:

/* max sum_{i=2到n} (vi*xi)

/* (1) sum_{i=2到n }(wi * Xi)& lt；= c - w1*y1

/* (2) xi∈{0，1}，2 & lt= i & lt=n

/*因为否则，子问题有最优解(Z2，Z3，..，Zn)。

/*和(y2，y3，...，yn)不是最优解。所以有:

/* sum_{i=2到n }(VI * zi)& gt；sum_{i=2到n} (vi*yi)

/* and，w 1 * y 1+sum _ { I = 2ton }(wi * zi)< = c

/*进一步:

/* v 1 * y 1+sum _ { I = 2 to n }(VI * zi)>sum_{i=1到n} (vi*yi)

/* w 1 * y 1+sum _ { I = 2 to n }(wi * zi)& lt；= c

/*这表明(y1，z2，z3，...zn)是给定的0-1背包问题的更好的解决方案，那么

/*它显示(y1，y2，...，yn)不是问题的最优解，与前提矛盾，所以是最优的。

/*子结构属性保持不变。

/*

/* 2.2子问题的重叠性质

/*设给定0-1背包问题的子问题P(i，j)为:

/* max sum_{k=i到n} (vk*xk)

/*(1)sum _ { k = I to n }(wk * xk)& lt；= j

/* (2) xk∈{0，1}，i & lt= k & lt=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 & gt=wn

/* m(n，j) = 0，0 & lt= j & lt营养良好的

/* B .递归公式m(i，j)

/*//背包容量为J，可选物品为I，i+1，...，n

/*//如果背包容量j

/* m(i，j) = m(i+1，j)，0 & lt= j & ltwi

/*//如果j & gt=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 & gt=wi

/*

/************************************************************************/

#定义max(a，b) (((a)>(b))？(a) : (b))

#定义min(a，b)(((a)& lt；(b))？(a) : (b))

模板& lttypename Type & gt

空背包(类型* v，int *w，int c，int n，类型**m)

{

//递归初始条件

int jMax = min(w[n] - 1，c)；

for(int j = 0；j & lt= jMaxj++) {

m[n][j]= 0；

}

for(j = w[n]；j & lt= c；j++) {

m[n][j]= v[n]；

}

//i从2到n-1，分别为J >；=wi和0

for(int I = n-1；我& gt1;我- ) {

jMax = min(w[i] - 1，c)；

for(int j = 0；j & lt= jMaxj++) {

m[I][j]= m[I+1][j]；

}

for(j = w[I]；j & lt= 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 & gt；= w[1]) {

m[1][c]= max(m[1][c]，m[2][c-w[1]]+v[1])；

}

}

模板& lttypename Type & gt

void回溯(类型**m，int *w，int c，int n，int* x)

{

for(int I = 1；我& ltn；i++) {

if(m[I][c]= = m[I+1][c])x[I]= 0；

否则{

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；我& ltn+1；i++) {

ppm[I]= new int[c+1]；

}

int x[6]；

背包& ltint & gt(钒、钨、碳、氮、百万分率)；

回溯& ltint & gt(ppm，w，c，n，x)；

返回0；

}

2.求解0-1背包问题的贪婪算法

1.贪婪方法的基本思想:

——从问题的一个初始解出发，逐步逼近给定的目标，从而尽快得到一个更好的解。当到达算法中的某个步骤时，算法停止。

这种算法存在一些问题:

1).不能保证最终的解决方案是最好的；

2).不能用来求最大或最小解的问题；

3).只能找到满足某些约束的可行解的范围。

实现这个算法的过程:

从问题的初始解决方案开始；

同时可以朝着既定的总体目标更进一步。

求可行解的解元素；

问题的可行解由所有解元素组成；

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

(1)根据贪婪策略，每次选择价值最大的物品放入背包。结果是最好的吗？

(2)每次选择占用空间最少的项目能否得到最优解？

(3)一次选择单位产能价值最大的项目成为解决这一问题的策略。

& lt程序代码:>(环境:c++)

# include & ltiostream.h & gt

#定义最大100 //最大项目数

Voidsort (int n，float a [max]，float b[max])//按值密度排序。

{

int j，h，k；

float t1，t2，t3，c[max]；

for(k = 1；k & lt= n；k++)

c[k]= a[k]/b[k]；

for(h = 1；h & ltn；h++)

for(j = 1；j & lt= n-h；j++)

if(c[j]& lt；c[j+1])

{ t 1 = a[j]；a[j]= a[j+1]；a[j+1]= t 1；

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背包(int n，float limitw，float v[max]，float w[max]，int x[max])

{ float c 1；//c1是背包剩余的可承载重量。

int I；

sort(n，v，w)；//项目按值密度排序。

c 1 = limitw；

for(I = 1；我& lt= n；i++)

{

if(w[I]& gt；c1)断开；

x[I]= 1；//当x [i]为1时，I项在解中。

c 1 = c 1-w[I]；

}

}

void main()

{int n，I，x[max]；

float v[max]，w[max]，totalv=0，totalw=0，limitw

cout & lt& lt"请输入n和limit w:"；

CIN & gt；& gtn & gt& gtlimitw

for(I = 1；我& lt= n；i++)

x[I]= 0；//项目选择表初始化为0。

cout & lt& lt"请依次输入项目的值:"

for(I = 1；我& lt= n；i++)

CIN & gt；& gt五[一]；

cout & lt& ltendl

cout & lt& lt"请依次输入物品的重量:"

for(I = 1；我& lt= n；i++)

CIN & gt；& gtw[I]；

cout & lt& ltendl

背包(n，limitw，v，w，x)；

cout & lt& lt"选择是:"；

for(I = 1；我& lt= n；i++)

{

cout & lt& ltx[I]；

if(x[i]==1)

total w = total w+w[I]；

}

cout & lt& ltendl

cout & lt& lt"背包的总重量是:" < & lttotalw & lt& ltendl//背包的总重量

cout & lt& lt"背包的总价值是:"

}

3.求解0-1背包问题的回溯算法

1.0-l背包问题是一个子集选择问题。

一般来说，0-1背包问题是一个NP难问题。0-1背包

问题的解空间可以用子集树来表示。求解0-1背包问题的回溯法与求解装载问题的回溯法非常相似。

比如。在搜索解空间树时，只要它的左子节点是可行节点，搜索就进入它的左子树。当...的时候

当右子树可能包含最优解时，就进入右子树搜索。否则，切掉右边的子树。设r为当前余数。

货物总价值；Cp是当前值；Bestp是目前最好的价值。当CP+R ≤ BETP时，右可截。

子树。计算右子树中解的上界的一个更好的方法是根据它们的单位权重值对剩余的项进行排序，然后

依次装载物品，直到装不下为止，然后再装载一部分物品填满背包。由此获得的值为

右子树中解的上界。

2.解决方案想法:

为了计算上界，我们可以先将物品按其单位重量值从大到小排序，然后只测试顺序。

检查所有的项目。实现时，通过bound计算当前节点的上界。在搜索解空间树时，只要它的左子节点是可行节点，搜索就进入左子树，右子树可能包含最优解后再进入右子树。否则，切掉右边的子树。

回溯是一种系统的、跳跃性的搜索算法。它按照深度优先的策略从包含问题所有解的解空间树的根节点开始搜索解空间树。算法在搜索解空间树的任意节点时，总是判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过系统对以该节点为根的子树的搜索，逐层追溯到其祖先节点。否则，进入子树，按照深度优先策略继续搜索。用回溯法求问题的所有解时，要回溯到根，一直搜索到根节点的所有子树，才结束。用回溯法求问题的任何解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法被称为回溯法，适用于解决一些组合数量较大的问题。

2.算法框架:

A.问题的解空间:应用回溯法解题时，首先要明确问题的解空间。问题的解空间应该是问题的至少包含的(最优)解。

B.回溯法的基本思想:回溯法在确定解空间的组织结构后，从起始节点(根节点)开始，以深度优先的方式搜索整个解空间。这个起始节点成为活节点，它也成为当前的扩展节点。在当前扩展节点处，搜索移动到深度方向上的新节点。这个新节点成为新的活节点，并成为当前的扩展节点。如果当前扩展节点不能再在深度方向上移动，则当前扩展节点成为死节点。换句话说，这个节点不再是活节点。此时，我们应该移回(回溯)到最近的活节点，并使这个活节点成为当前的扩展节点。回溯法就是以这种方式在解空间中递归搜索，直到找到所需解或者解空间中没有活节点。

3.用回溯法解题通常包括以下三个步骤:

a .针对给定的问题，定义问题的解空间；

b .确定易于搜索的解空间结构；

c .以深度优先的方式搜索解空间，在搜索过程中使用剪枝函数避免无效搜索；

# include & ltiostream & gt

使用命名空间std

类别Knap

{

friend int背包(int p[]，int w[]，int c，int n)；

公共:

作废打印()

{

for(int m = 1；m & lt= n；m++)

{

cout & lt& ltbestx[m]& lt；& lt" ";

}

cout & lt& ltendl

};

私人:

int Bound(int I)；

void回溯(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裂隙= c-CW；//剩余容量

int b = cp

//按照每单位重量价值的降序来装载物品。

while(我& lt= n & amp& ampw[I]& lt；=裂缝)

{

裂-= w[I]；

b+ = p[I]；

i++；

}

//装满你的背包。

如果(我& lt=n)

b+ = p[I]/w[I]*裂；

返回b；

}

void Knap::Backtrack(int i)

{

如果(i & gtn)

{

if(bestp & lt；cp)

{

for(int j = 1；j & lt= n；j++)

bestx[j]= x[j]；

bestp = cp

}

返回；

}

if(CW+w[I]& lt；=c) //搜索左侧子树

{

x[I]= 1；

CW+= w[I]；

CP+= p[I]；

回溯(I+1)；

CW-= w[I]；

CP-= p[I]；

}

if(Bound(i+1)>Bestp)//搜索右边的子树

{

x[I]= 0；

回溯(I+1)；

}

}

类对象

{

friend int背包(int p[]，int w[]，int c，int n)；

公共:

int运算符& lt=(对象a)常量

{

return(d & gt；= a . d)；

}

私人:

int ID

浮动d；

};

int背包(int p[]，int w[]，int c，int n)

{

//初始化Knap::Backtrack

int W = 0；

int P = 0；

int I = 1；

Object * Q =新对象[n]；

for(I = 1；我& lt= n；i++)

{

Q[i-1]。ID = I；

Q[i-1]。d = 1.0 * p[I]/w[I]；

p+= p[I]；

w+= w[I]；

}

如果(W & lt=c)

返回P；//加载所有项目

//按项目单位重量排序

浮动f；

for(I = 0；我& ltn；i++)

for(int j = I；j & ltn；j++)

{

if(Q[i].d & ltQ[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；我& lt= 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.回溯(1)；

k . print()；

删除[]Q；

删除[]k . w；

删除[]k . p；

返回K.bestp

}

void main()

{

int * p；

int * w；

int c = 0；

int n = 0；

int I = 0；

char k；

cout & lt& lt“0-1背包问题-回溯法”

cout & lt& lt“by zbqplayer”& lt；& ltendl

当(k)

{

cout & lt& lt"请输入背包容量(c):"

CIN & gt；& gtc；

cout & lt& lt"请输入项目数(n):"

CIN & gt；& gtn；

p = new int[n+1]；

w = new int[n+1]；

p[0]= 0；

w[0]= 0；

cout & lt& lt"请输入项目的值(p):"

for(I = 1；我& lt= n；i++)

CIN & gt；& gtp[I]；

cout & lt& lt"请输入物品的重量(w):"

for(I = 1；我& lt= n；i++)

CIN & gt；& gtw[I]；

cout & lt& lt"最优解是(bestx):"

cout & lt& lt"最佳值是(bestp):"

cout & lt& lt背包(p，w，c，n)& lt；& ltendl

cout & lt& lt"[s]重新开始"

cout & lt& lt"[q]退出"

CIN & gt；& gtk；

}

4.求解0-1背包问题的分枝定界法

1.问题描述:已知有n个物品和一个能装m个重量的背包，每个物品I都有重量，一个物品只能放进去或者放不进去。解决如何摆放物品，可以最大化背包中物品的总收益。

2.设计思路及分析:是否选择项构成解树，左子树表示不加载，右图表示加载。通过搜索问题的解树，得到最优解，通过节点的上界杀死不满足要求的节点。

# include & ltiostream.h & gt

结构良好

{

int重量；

利息收益；

int标志；//标签可以加载吗？

};

int number = 0；//项目数

int up bound = 0；

int curp=0，curw = 0；//当前收益值和权重

int maxweight = 0；

好*包=空；

void Init_good()

{

包=新货[编号]；

for(int I = 0；我& lt号码；i++)

{

cout & lt& lt"请输入项目"

CIN & gt；& gt包[我]。重量；

cout & lt& lt"请输入项目"

CIN & gt；& gt包[我]。受益；

包[我]。flag = 0；//最初的标记是没有背包。

cout & lt& ltendl

}

}

Int get bound (int num，int * bound _ u)//返回该节点的c和u边界。

{

for(int w=curw，p = curpnum & lt数量和数量。& amp(w+bag[num]。重量)& lt= maxweightnum++)

{

w = w+袋子[数量]。重量；

p = w+袋子[数量]。受益；

}

*bound_u=p+bag[num]。受益；

返回(p+包[编号])。收益*(最大重量-w)/袋子[数量]。重量))；

}

无效LCbag()

{

int bound_u=0，bound _ c = 0；//当前节点的C和U边界

for(int I = 0；我& lt号码；I++)//逐层遍历解决方案树，决定是否加载每一项。

{

if( ( bound_c=getbound(i+1，& ampbound _ u))& gt；Upbound )//遍历左边的子树

upbound = bound _ u；//在不更改标志的情况下更改现有的U标尺。

if( getbound(i，& ampbound_u)>Bound_c )//遍历右边的子树

//如果加载，则判断右侧子树根的c间隙是否大于左侧子树根的c间隙；如果是，则加载它。

{

upbound = bound _ u；//更改现有的U标尺。

curp=curp+bag[i]。受益；

curw=curw+bag[i]。重量；//从现有权重和收益中添加新项目。

包[我]。flag = 1；//标记为已加载

}

}

}

空显示()

{

cout & lt& lt“背包能装的物品数量是”；

for(int I = 0；我& lt号码；i++)

如果(包[我]。flag & gt0)

cout & lt& ltI+1 & lt；& lt" ";

cout & lt& ltendl

删除[]包；

}