再问个01背包问题（也是回溯法实现）
图中给出3件物品（n）, C是背包的容量，W，V就是1~n件物品的重量和价值。相近的解题方法如下：
#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 << " ";
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<=cleft)
{
cleft -= w;
b += p;
++i;
}
//装满背包时
if(i<=n) b += p/w*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;++j)
bestx = x;
bestp = cp;
}
return;
}
if(cw+w<=c) //搜索左子树
{
x = 1;
cw += w;
cp += p;
Backtrack(i+1);
cw -= w;
cp -= p;
}
if(Bound(i+1)>bestp) //搜索右子树
{
x = 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)
{
int W = 0;
int P = 0;
int i = 1;
Object *Q = new Object;
for(i=1;i<=n;++i)
{
Q.ID = i;
Q.d = 1.0*p/w;
P += p;
W += w;
}
if(W<=c)
return P; //装入所有物品
//依物品单位重量排序
float f;
for(i=0;i<n;++i)
for(int j=i;j<n;++j)
{
if(Q.d<Q.d)
{
f = Q.d;
Q.d = Q.d;
Q.d = f;
}
}
Knap K;
K.p = new int;
K.w = new int;
K.x = new int;
K.bestx = new int;
K.x = 0;
K.bestx = 0;
for(i=1;i<=n;++i)
{
K.p = p.ID];
K.w = w.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;
}
int main(void)
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
cout << "请输入物品个数n：" << endl;
cin >> n;
p = new int;
w = new int;
p = 0;
w = 0;
cout << "请输入n个物品的价值:" << endl;
for(i=1;i<=n;++i)
cin >> p;
cout << "请输入N个物品的重量：" << endl;
for(i=1;i<=n;++i)
cin >> w;
cout << "请输入背包容量：" << endl;
cin >> c;
cout << Knapsack(p,w,c,n) << endl;
system("PAUSE");
return 0;
}
还是比较多不懂的地方，像类里面的Bound方法最后那句://装满背包时
if(i<=n) b += p/w*cleft;
第i物品的价值/第i物品的重量*背包剩余容量是什么意思？
在这个IF之前的循环不是已经把重量都得到了吗？
还有就是它到底是怎么分别左右子树的？ 晕晕的 这个算法的关键是把单个物品的价值最大的计算出来即p/w，然后放入到包中p/w*cleft，为确保有足够的空间，所以要IF一下，然后再放入包中,b += p/w*cleft; 还是不明白,单个物品的价值最大的计算出来? p不就是这物品的价值了吗？
p是总体价值,不是单数价值 C++还只是学了点皮毛，这程序看得很吃力。于是把它转成C语言描述了。
#include<stdio.h>
#include<stdlib.h>
int content; //背包容量
int n; //物品数
int *weight; //存放n个物品重量的数组
int *price; //存放n个物品价值的数组
int currentWeight;//当前重量
int currentPrice; //当前价值
int bestPrice; //当前最优值
int *bestAnswer; //当前最优解
int *cAnswer; //当前解
int Bound(int i) //检验子树是否能产生合适解的函数
{
int cleft = content - currentWeight; //求背包剩余容量
int p = currentPrice; //当前背包所装物品价值
while(i<=n && weight<=cleft)
{
cleft -= weight;
p += price;
++i;
}
return p; //返回价值p
}
void Backtracking(int i)
{
int j;
if(i>n)
{
if(bestPrice<currentPrice) //最优值小于当前价值则赋值
{
for(j=1;j<=n;++j)
bestAnswer = cAnswer; //取得树上路径
bestPrice = currentPrice;
}
return;
}
if(currentWeight+weight<=content)//当前重量+该物品重量 <= 背包容量
{
//搜索左子树
cAnswer = 1;
currentWeight += weight;
currentPrice += price;
Backtracking(i+1);
//完成上面的递归，返回到上一结点，准备递归右子树
currentWeight -= weight;
currentPrice -= price;
}
if(Bound(i+1)>bestPrice) //搜索右子树，如返回值大于当前最优值，则执行
{
cAnswer = 0;
Backtracking(i+1);
}
}
void Print()
{
int i;
printf("\\n\\nthe bestAnswer={");
for(i=1;i<n;++i)
printf("%d,",bestAnswer);
printf("%d}\\tthe bestPrice=%d\\n",bestAnswer,bestPrice);
}
void Destroy() //销毁分配空间
{
free(price);
free(weight);
free(bestAnswer);
free(cAnswer);
}
int main(void)
{
int i;
//输入物品数量
printf("please enter article amount:\\n");
scanf("%d",&n);
//输入物品价格
printf("please enter all articles price:\\n");
if(!(price=(int*)malloc((n+1)*sizeof(int)))) exit(1);
for(i=1;i<=n;++i)
scanf("%d",&price);
//输入物品重量
printf("please enter all articles weight:\\n");
if(!(weight=(int*)malloc((n+1)*sizeof(int)))) exit(1);
for(i=1;i<=n;++i)
scanf("%d",&weight);
//输入背包容量
printf("please enter knapsack's content:\\n");
scanf("%d",&content);
if(!(bestAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
if(!(cAnswer=(int*)malloc((n+1)*sizeof(int)))) exit(1);
Backtracking(1);//回溯法搜索最优解
Print(); //打印结果
Destroy();
system("PAUSE");
return 0;
}
页:
[1]