加载中…0-1背包问题简单实例（回溯法求解）
(2011-12-07 15:35:11)
标签：
节点最优值左子树utf-8回溯杂谈 |
bag2.cpp
#include <iostream>
using namespace std;
class Object;
template <class Typew, class
Typep>
Typep Knapsack(Typep *p, Typew *w, Typew c, int n);
void MergeSort(Object *, int);
class Object
{
public:
int operator <= (Object a)const
{
return (d >= a.d);
}
int ID;
float d;
};
template <class Typew, class
Typep>
class Knap
{
public:
Typep Bound(int);
void Backtrack(int );
Typew c;//weight constrain of the bag
int n;//number of kinds of goods
Typew *w;//weiht of goods
Typep *p;//value of goods
Typew cw;//current weight of the bag
Typep cp;//current value of the bag
Typep bestp;//current optimal value of the bag
};
template <class Typew, class
Typep>
Typep Knap<Typew,
Typep>::Bound(int i)
{
Typew cleft = c - cw;//weight left of the bag
Typep b = cp;
//add the weight of goods in decreasing order
while(i <= n &&
w[i] <= cleft)
{
cleft -= w[i];
b += p[i];
i ++;
}
if(i <= n)
{
b += p[i] * cleft / w[i];
}
return b;
}
template <class Typew, class
Typep>
void Knap<Typew,
Typep>::Backtrack(int i)
{
if(i > n)
{
bestp = cp;
return ;
}
if(cw + w[i] <= c)
{
//enter the left subtree
cw += w[i];
cp += p[i];
Backtrack(i + 1);
cw -= w[i];
cp -= p[i];
}
if(Bound(i + 1) > bestp)
{
Backtrack(i + 1);
}
}
int main()
{
//0-1 bag problem, using backtrack method
int c;//weight constrain of the bag
int *v;//value of goods
int n;//kinds of goods
int i, j;
cout<<"Please input weight
constrain of the bag:";
cin>>c;
cout<<"Please input number of
kinds of goods:";
cin>>n;
if(n <= 0 || c <= 0)
{
cout<<"invalid
arguments"<<endl;
return 0;
}
cout<<"Please input
"<<n<<"
weight of goods:"<<endl;
w = new int[n + 1];
w[0] = 0;
for(i = 1; i <= n; i++)
{
cin>>w[i];
}
cout<<"Please input
"<<n<<"
value of goods:"<<endl;
v = new int[n + 1];
v[0] = 0;
for(i = 1; i <= n; i++)
{
cin>>v[i];
}
int temp = Knapsack(v, w, c, n);
cout<<"The optimal value is:
"<<temp<<endl;
delete w;
delete v;
return 0;
}
template <class Typew, class
Typep>
Typep Knapsack(Typep *p, Typew *w, Typew c, int n)
{
int i;
Typew W = 0;
Typep P = 0;
Object *Q = new Object[n + 1];
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;
}
MergeSort(Q, n);
Knap<Typew, Typep> K;
K.p = new Typep[n + 1];
K.w = new Typew[n + 1];
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);
delete []Q;
delete []K.w;
delete []K.p;
return K.bestp;
}
void MergeSort(Object *Q,int n)
{
for(int i = 0;i < n;i++)
{
int s = i;
for(int j = i + 1;j < n;j++)
if(Q[j].d > Q[s].d)
s = j;
Object temp=Q[i];
Q[i] = Q[s];
Q[s] = temp;
}
}
Makefile：
bag2:bag2.o
g++ -o bag2 bag2.o
bag2.o:bag2.cpp
g++ -c bag2.cpp
运行结果：
Please input weight constrain of the bag:10
Please input number of kinds of goods:5
Please input 5 weight of goods:
2
2
6
5
4
Please input 5 value of goods:
6
3
5
4
6
The optimal value is: 15
喜欢
0
赠金笔
后一篇：快速排序（整型版本）