我在做毕业设计,但是里面涉及到背包算法问题,因为我没有学过这个,希望能够得到大家帮助,我在这里谢谢大家了!下面给出一个VC的背包回溯算法:
#include "iostream.h"
class knap{
friend int knapsack(int *,int *,int,int);
private:
int bound(int i);
void backtrack(int i);
int c,n,*w,*p,cw,cp,bestp;
                      };int knap::bound(int i)
{
int cl=c-cw;
int b=cp;
while(i<=n&&w[i]<=cl)
{
                                  cl-=w[i];b+=p[i++];
                                     }
if(i<=n)b+=p[i]/w[i]*cl;
return b;
}void knap::backtrack(int i)
{
if(i>n)
{
                                   bestp=cp;
                                   return;
                                         }
if(cw+w[i]<=c)
                                         {
cw+=w[i];
                                cp+=p[i];
backtrack(i+1);
cw-=w[i];
cp-=p[i];
                                           }
if(bound(i+1)>bestp)
                backtrack(i+1);}class object{
friend int knapsack(int *,int *,int,int);
friend void sort(object *p,int n);
public:
int operator <=(object a) const
{return(d<=a.d);}
private:
int id;
float d;};void sort(object *q,int n)
{for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(q[i]<=q[j]){
object t=q[i];
                                                                q[i]=q[j];
                                                                q[j]=t;}
}int knapsack(int *p,int *w,int c,int n){
int W=0,P=0;
object *Q=new object[n];
for(int i=1;i<=n;i++){
Q[i-1].id=i;
Q[i-1].d=p[i]/w[i];
P+=p[i];
W+=w[i];}
if(W<=c)return P;