本文目录一览：
- 1、编程序解决0 1 背包问题？（c语言）
- 2、关于C++ 01背包问题
- 3、c语言0-1背包问题高手进来
- 4、0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）
- 5、0-1背包问题到底能用贪心法解决吗？
- 6、贪心算法解决特殊0-1背包问题
编程序解决0 1 背包问题？（c语言）
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace beibao
{
class np
{
private int c = 0;//容量
private wp[] w;//物品
private int cp = 0;//当前价值
private int cw = 0;//当前重量
private int bestp = 0;//当前最优值
///动态规划中/////////////
private int[] head; //辅助数组
private int[,] p; //辅助数组
public np(wp[] w,int c)
{
p = new int[9999, 2];
this.w = w;
this.c = c;
sort();
tanxin();
huisu();
dongtaiguihua();
}
public void sort()
{
wp wupin;
for (int i = 0; i w.Length-1; i++)
{//从小到大冒泡排序
for (int j = 0; j w.Length-i-1; j++)
{
if (w[i].danweizhongliang w[i + 1].danweizhongliang)
{
wupin = w[i];
w[i] = w[i + 1];
w[i + 1] = wupin;
}
}
}
}
public void tanxin()
{
cp = cw = bestp = 0;
for (int i = 0; i w.Length; i++)
{
w[i].State = false;
}
for (int i = 0; i w.Length; i++)
{
if (cw + w[i].Weight c)
continue;
cw += w[i].Weight;
cp += w[i].Price;
w[i].State = true;
}
Console.WriteLine("贪心算法:装入价值"+cp.ToString());
Console.WriteLine("装入物品号码:");
for (int i = 0; i w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
public void huisu()
{
cp = cw = bestp = 0;
for (int i = 0; i w.Length; i++)
{
w[i].State = false;
}
Backtrack(0);
Console.WriteLine("回溯法:装入价值" + bestp.ToString());
Console.WriteLine("装入物品号码:");
for (int i = 0; i w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
private void Backtrack(int i)
{
if (i = w.Length)
{
bestp = cp; return;
}
if (cw + w[i].Weight = c)
{
cw += w[i].Weight;
cp += w[i].Price;
w[i].State = true;
Backtrack(i + 1);
cw -= w[i].Weight;
cp -= w[i].Price;
}
if (Bound(i + 1) bestp)
{
Backtrack(i + 1); w[i].State = false;
}
}
private double Bound(int i)
{
int cleft = c - cw;
double b =(double ) cp;
while (i w.Length w[i].Weight = cleft)
{
cleft -= w[i].Weight;
b += w[i].Price;
i++;
}
if (i w.Length)
{
b += (double)w[i].Price * (double)cleft / (double)w[i].Weight;
}
return b;
}
public void dongtaiguihua()
{
cp = cw = bestp = 0;
for (int i = 0; i w.Length; i++)
{
w[i].State = false;
}
int m= Knapsack(w.Length);
Console.WriteLine("动态规划:装入价值" + m.ToString());
Console.WriteLine("装入物品号码:");
for (int i = 0; i w.Length; i++)
{
if (w[i].State == true) Console.Write(w[i].number.ToString() + "\t");
} Console.WriteLine();
}
private int Knapsack(int n)
{
head = new int[n + 2];
head[n + 1] = 0;
p[0, 0] = 0;
p[0, 1] = 0;
int left = 0;
int right = 0;
int next = 1;
head[n] = 1;
for (int i =n-1; i = 0; i--)
{
int k = left;
for (int j = left; j = right; j++)
{
if (p[j, 0] + w[i].Weight c)
break;
int y = p[j, 0] + w[i].Weight;
int m = p[j, 1] + w[i].Price;
while (k = right p[k, 0] y)
{
p[next, 0] = p[k, 0];
p[next++, 1] = p[k++, 1];
}
if (k = right p[k, 0] == y)
{
if (m p[k, 1]) m = p[k, 1];
k++;
}
if (m p[next - 1, 1])
{
p[next, 0] = y;
p[next++, 1] = m;
}
while (k = right p[k, 1] = p[next - 1, 1])
k++;
}
while (k = right)
{
p[next, 0] = p[k, 0];
p[next++, 1] = p[k++, 1];
}
left = right + 1;
right = next - 1;
head[i] = next;
}
Traceback(n);
return p[next - 1, 1];
}
private void Traceback(int n)
{
int j = p[head[0] - 1, 0];
int m = p[head[0] - 1, 1];
for (int i = 0; i n; i++)
{
w[i].State = false;
for (int k = head[i + 1]; k = head[i] - 1; k++)
{
if (p[k, 0] + w[i].Weight == j p[k, 1] + w[i].Price == m)
{
w[i].State = true;
j = p[k, 0];
m = p[k, 1];
break;
}
}
}
}
}
/// summary
/// 物品类
/// /summary
class wp
{
private int w = 0;
private int p = 0;
private int num;
private bool state=false;
public wp(int w,int p,int n)
{
this.w = w;
this.p = p;
num = n;
}
public int Weight
{
get
{
return w;
}
}
public int Price
{
get
{
return p;
}
}
public bool State
{
set
{
state = value;
}
get
{
return state;
}
}
public double danweizhongliang
{
get
{
return (double)p / (double)w;
}
}
public int number
{
get
{
return num;
}
}
}
}
//////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace beibao
{
class Program
{
static void Main(string[] args)
{
np beobap;
int n = 0;
Console.WriteLine("物品数量");
n = Convert.ToInt32(Console.ReadLine());
wp[] wupin = new wp[n];
int c = 0;
Console.WriteLine("背包容积");
c = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i n; i++)
{//初始化
int w = 0; int p = 0;
Console.WriteLine("物品" + (i + 1) + "的重量");
w = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("物品" + (i + 1) + "的价值");
p = Convert.ToInt32(Console.ReadLine());
wupin[i] = new wp(w, p, i);
}
beobap = new np(wupin, c);
}
}
}
这是当初我上学的时候做的，应该没什么问题，你看看还可以修改修改，有什么问题可以再问我
关于C++ 01背包问题
1. 摘要
以背包问题为例，介绍了贪心法与动态规划的关系以及两个方案在解决背包问题上的比较。贪心法什么时候能取到最优界并无一般理论，但对于普通背包问题我们有一个完美的结果——贪心法可取到最优解。介绍了其它一些对背包问题的研究或者拓展。
2. 介绍
贪心算法是我们在《算法设计技巧与分析》这门课中所学习到的几种重要的算法之一，顾名思义，贪心算法总是作出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。
3. 算法思想:
贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
在约束 下最大。
(2) 动态规划解决方案：是解决0/1背包问题的最优解
(i) 若i=0或j=0, V[i,j] = 0
(ii) 若jsi, V[i,j] = V[i-1,j] (仅用最优的方法，选取前i-1项物品装入体积为j 的背包，因为第i项体积大于j,装不下这一项，所以背包里面的i-1项就达到最大值)
(iii) 若i0和j=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一种情况是包中的i-1项已经达到最大值，第二种情况是i-1项占j-si的体积再加上第i项的总的价值，取这两种情况的最大值。)
//sj和vj分别为第j项物品的体积和价值，C是总体积限制。
//V[i,j]表示从前i项{u1,u2,…,un}中取出来的装入体积为j的背包的物品的最大//价值。[13]
（3）贪心算法解决背包问题有几种策略：
(i) 一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii) 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii) 还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。
而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
如图1，大体上说明了动态规划解决的0／1背包问题和贪心算法解决的问题之间的区别，
图1
（4）贪心算法解决背包问题的算法实现：
代码如下：
#include iostream.h
struct goodinfo
{
float p; //物品效益
float w; //物品重量
float X; //物品该放的数量
int flag; //物品编号
};//物品信息结构体
void Insertionsort(goodinfo goods[],int n)
{//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序
int j,i;
for(j=2;j=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].pgoods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}//按物品效益，重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
float cu;
int i,j;
for(i=1;i=n;i++)
goods[i].X=0;
cu=M; //背包剩余容量
for(i=1;in;i++)
{
if(goods[i].wcu)//当该物品重量大与剩余容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//确定背包新的剩余容量
}
if(i=n)
goods[i].X=cu/goods[i].w;//该物品所要放的量
/*按物品编号做降序排列*/
for(j=2;j=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].flaggoods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
///////////////////////////////////////////
cout"最优解为:"endl;
for(i=1;i=n;i++)
{
cout"第"i"件物品要放:";
coutgoods[i].Xendl;
}
}
void main()
{
cout"|--------运用贪心法解背包问题---------|"endl;
int j,n; float M;
goodinfo *goods;//定义一个指针
while(j)
{
cout"请输入物品的总数量：";
cinn;
goods=new struct goodinfo [n+1];//
cout"请输入背包的最大容量：";
cinM;
coutendl;
int i;
for(i=1;i=n;i++)
{ goods[i].flag=i;
cout"请输入第"i"件物品的重量:";
cingoods[i].w;
cout"请输入第"i"件物品的效益:";
cingoods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
coutendl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout"press 1 to run agian"endl;
cout"press 0 to exit"endl;
cinj;
}
}
c语言0-1背包问题高手进来
#include "stdio.h"
#include "time.h"
#define BOXMAX 10
typedef struct BOX
{
int locate[BOXMAX];
float weight[BOXMAX];
float price[BOXMAX];
int n;
}box;
void main()
{
box bx;
int sign=0;
int row,line;
int maxbox;
int tmp;
float maxvalue=0;
int b_n;
float input;
float b_total;
float gotcount=0;
srand(time(NULL));
while(!sign)
{
printf("input the number of bpx:");
scanf("%d",b_n);
printf("\nintput the weight of box:");
scanf("%f",b_total);
if(b_n=BOXMAX)
{
sign=1;
}
}
printf("\ninput the weight:");
for(row=0;rowb_n;row++)
{
/*
bx.locate[row]=row+1;
bx.weight[row]=rand()%10+1;
bx.price[row]=rand()%10+1;
*/
bx.locate[row]=row+1;
scanf("%f",bx.weight[row]);
}
printf("\ninput the price:");
for(row=0;rowb_n;row++)
{
scanf("%f",bx.price[row]);
}
printf("\n\n\nwithout order\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.locate[row]);
}
printf("\nweight:\n");
printf("\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.weight[row]);
}
printf("\nprice:\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.price[row]);
}
for(row=0;rowb_n-1;row++)
{
maxvalue=bx.price[row]/bx.weight[row];
maxbox=row;
for(line=row+1;lineb_n;line++)
{
if((bx.price[line]/bx.weight[line])maxvalue)
{
maxvalue=bx.price[line]/bx.weight[line];
maxbox=line;
}
}
if(maxbox!=row)
{
tmp=bx.weight[row];
bx.weight[row]=bx.weight[maxbox];
bx.weight[maxbox]=tmp;
tmp=bx.price[row];
bx.price[row]=bx.price[maxbox];
bx.price[maxbox]=tmp;
tmp=bx.locate[row];
bx.locate[row]=bx.locate[maxbox];
bx.locate[maxbox]=tmp;
}
}
printf("\n\n\nlist order\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.locate[row]);
}
printf("\n");
printf("\nweight:\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.weight[row]);
}
printf("\nprice:\n");
for(row=0;rowb_n;row++)
{
printf("%4d",(int)bx.price[row]);
}
row=0;
while(b_total=bx.weight[row])
{
b_total=b_total-bx.weight[row];
gotcount+=bx.price[row];
row+=1;;
}
getcount+=(b_total/bx.weight[row])*bx.price[row];
printf("\n\n%d",(int)gotcount);
getch();
getch();
}
上面一点注释都没有 呵呵 但主要思想可以给你说一下 就是 贪心酸法 选取最高性价比的 填入 箱子；
箱子输入所有重量 单位价格之后 排序 按照 性价比最高的 一次填入；
0-1背包问题的多种解法代码（动态规划、贪心法、回溯法、分支限界法）
一.动态规划求解0-1背包问题
/************************************************************************/
/* 0-1背包问题：
/* 给定n种物品和一个背包
/* 物品i的重量为wi，其价值为vi
/* 背包的容量为c
/* 应如何选择装入背包的物品，使得装入背包中的物品
/* 的总价值最大？
/* 注：在选择装入背包的物品时，对物品i只有两种选择，
/* 即装入或不装入背包。不能将物品i装入多次，也
/* 不能只装入部分的物品i。
/*
/* 1. 0-1背包问题的形式化描述：
/* 给定c0, wi0, vi0, 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=jwn
/* b. 递归式 m(i,j)
/* //背包容量为j、可选物品为i,i+1,...,n
/* //如果背包容量jwi，则根本装不进物品i，所以有：
/* m(i,j) = m(i+1,j), 0=jwi
/* //如果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=jwi即使m(i,j)
for (int i=n-1; i1; 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; in; 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; in+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsackint(v, w, c, n, ppm);
TraceBackint(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++)
#includeiostream.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;hn;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:";
cinn limitw;
for(i=1;i=n;i++)
x[i]=0; //物品选择情况表初始化为0
cout"请依次输入物品的价值："endl;
for(i=1;i=n;i++)
cinv[i];
coutendl;
cout"请依次输入物品的重量："endl;
for(i=1;i=n;i++)
cinw[i];
coutendl;
knapsack (n,limitw,v,w,x);
cout"the selection is:";
for(i=1;i=n;i++)
{
coutx[i];
if(x[i]==1)
totalw=totalw+w[i];
}
coutendl;
cout"背包的总重量为："totalwendl; //背包所装载总重量
cout"背包的总价值为："totalvendl; //背包的总价值
}
三.回溯算法求解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.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
#includeiostream
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++)
{
coutbestx[m]" ";
}
coutendl;
};
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=nw[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(in)
{
if(bestpcp)
{
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;in;i++)
for(int j=i;jn;j++)
{
if(Q[i].dQ[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;
cinc;
cout"请输入物品的个数(n)："endl;
cinn;
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++)
cinp[i];
cout"请输入物品的重量(w)："endl;
for(i=1;i=n;i++)
cinw[i];
cout"最优解为(bestx)："endl;
cout"最优值为(bestp)："endl;
coutKnapsack(p,w,c,n)endl;
cout"[s] 重新开始"endl;
cout"[q] 退出"endl;
cink;
}
四.分支限界法求解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; inumber; i++)
{
cout"请输入第件"i+1"物品的重量:";
cinbag[i].weight;
cout"请输入第件"i+1"物品的效益:";
cinbag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
coutendl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; numnumber (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; inumber; 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; inumber; i++)
if(bag[i].flag0)
couti+1" ";
coutendl;
delete []bag;
}
0-1背包问题到底能用贪心法解决吗？
0-1背包问题不能用贪心法解决，但是部分背包问题可以用贪心法解决。首先0-1背包是要么不拿，要拿就得把这类物品全部拿完。网页链接可以参考这个看看
贪心算法解决特殊0-1背包问题
void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]为每个物品的重量，c为背包容量
{
int i;
for(i=1;i=n;i++) x[i]=0;
for(i=1;i=n;i++)
{
if(w[i]c) break;
x[i]=1;
c-=w[i];
}
}
