anpai.h

用回溯法求解0—1背包问题

// ANPAI.h: interface for the CANPAI class.
//
//////////////////////////////////////////////////////////////////////
//回溯法解决0-1背包问题
//linxiaomengdi 2008.4.8
//[e-mail]
#if !defined(AFX_ANPAI_H__0B45EC15_6DA4_42DD_9A94_D194D6ABCC50__INCLUDED_)
#define AFX_ANPAI_H__0B45EC15_6DA4_42DD_9A94_D194D6ABCC50__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include<iostream>
using namespace std;

class Knap
{
	//设置友元函数
friend int Knapsack(int p[],int w[],int c,int n ,int AFlag[]); 

public:

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; //当前解

};


class Object
{
friend int Knapsack(int p[],int w[],int c,int n,int AFlag[]);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}

private:
int ID;
float d;
};



#endif // !defined(AFX_ANPAI_H__0B45EC15_6DA4_42DD_9A94_D194D6ABCC50__INCLUDED_)