greedy_bagdlg.cpp

背包算法

// greedy_bagDlg.cpp : implementation file
//

#include "stdafx.h"
#include "greedy_bag.h"
#include "greedy_bagDlg.h"
#include "time.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();
	
	// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA
	
	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL
	
	// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CGreedy_bagDlg dialog

CGreedy_bagDlg::CGreedy_bagDlg(CWnd* pParent /*=NULL*/)
: CDialog(CGreedy_bagDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CGreedy_bagDlg)
	m_k = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	
	//初始化数组
	A[0]=100;
	for(int i=1;i<140;i++)
		A[i]=0;
	//
	AllValue=0;
	AllWeight=100;
	Weight=0;
	temp_value=temp_weight=0;
	for(i=0;i<100;i++)
		BB[i]=999;
}

void CGreedy_bagDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CGreedy_bagDlg)
	DDX_Control(pDX, IDC_RESULT, m_result);
	DDX_Control(pDX, IDC_GOODS, m_goods);
	DDX_Text(pDX, IDC_K, m_k);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CGreedy_bagDlg, CDialog)
//{{AFX_MSG_MAP(CGreedy_bagDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CGreedy_bagDlg message handlers

BOOL CGreedy_bagDlg::OnInitDialog()
{
	CDialog::OnInitDialog();
	
	// Add "About..." menu item to system menu.
	
	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);
	
	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}
	
	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CGreedy_bagDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CGreedy_bagDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting
		
		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
		
		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;
		
		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CGreedy_bagDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CGreedy_bagDlg::OnOK() 
{
	A[0]=100;
	for(int i=1;i<140;i++)
		A[i]=0;
	//
	AllValue=0;
	AllWeight=100;
	Weight=0;
	temp_value=temp_weight=0;
	for(i=0;i<30;i++)
		BB[i]=999;
	///////
	UpdateData(1);//攻取k的值
	m_goods.ResetContent();
	m_result.ResetContent();
	//步骤一:产生随机物品
	GoodsInfo *goods;
	goods=MyBuilt();//产生随机物品
	CString temp;
	//步骤二:排序
	long BeginTime=clock();
	MySort(goods,100);
	for(i=0;i<100;i++)
	{
		temp.Format("%3d %8d %8d       %4f",goods[i].index+1,goods[i].p,goods[i].w,((double)goods[i].p)/((double)goods[i].w));
		m_goods.AddString(temp);
	}
	//步骤三:产生子集合并计算
	Combination(goods,100,m_k+1);
	if(Weight<AllWeight)//子集累加完以后若还未装完则继续装
	{
		int jj=0;
		while(Weight<AllWeight&&jj<100)//继续装直到装满
		{
			if(1!=BB[jj])
			{
				Weight+=goods[jj].w;
				AllValue+=goods[jj].p;
				if(Weight>AllWeight)//对剩下的物品一个个加入背包,如果大于背包总重量则换下一个物品
				{
					Weight-=goods[jj].w;
					AllValue-=goods[jj].p;
					jj++;
					continue;
				}
				BB[jj]=1;//标记为已放入
			}
			jj++;
		}
	}
	long endTime=clock();
	endTime-=BeginTime;
	//步骤四:输出
	temp.Format("总价值为:%4d",AllValue);
	m_result.AddString(temp);
	temp.Format("总重量为:%4d",Weight);
	m_result.AddString(temp);
	temp.Format("运行时间为:%4d",endTime);
	m_result.AddString(temp);
	m_result.AddString("加入背包的货物为有:");
	for(i=0;i<100;i++)
		if(1==BB[i])
		{
			temp.Format("%3d %8d %8d       %f",goods[i].index+1,goods[i].p,goods[i].w,((double)goods[i].p)/((double)goods[i].w));
			m_result.AddString(temp);
		}
		delete []goods;
		
}
GoodsInfo *CGreedy_bagDlg::MyBuilt()//产生随机物品
{
	GoodsInfo *goods=new GoodsInfo[100];//定义货物指针
	srand((unsigned)time( NULL ));
	int a,b;
	double c,d;
	for(int i=0;i<100;i++)
	{
		goods[i].index=i;
		a = rand()%10000;
		b = rand()%10000;
		c = (double)a/10000.0;
		d = (double)b/10000.0;
		goods[i].p=(int)(1+c*29);
		goods[i].w=(int)(1+d*29);
		goods[i].x=0;
	}
	return goods;
}

void CGreedy_bagDlg::MySort(GoodsInfo goods[],int n)//按物品价值重量比从大到小排序
{
	int i,j;
	GoodsInfo temp;
	for(i=1;i<n;i++)
	{
		temp=goods[i];
		j=i-1;
		while(double(temp.p)/double(temp.w)>double(goods[j].p)/double(goods[j].w)&&j>-1)
		{
			goods[j+1]=goods[j];
			j--;
		}
		goods[j+1]=temp;
	}
}	
char str[3];
void CGreedy_bagDlg::Combination(GoodsInfo goods[],int m,int k)//产生子集合
{
	int i;
	for(i=m;i>=k;i--)
	{
		A[k]=i;
		if(k>1)
			Combination(goods,i-1,k-1);
		else
		{
			for(int j=A[0];j>=1;j--)//累加一个子集合的重量与价值.
			{
				if(A[j])
				{		
					temp_value+=goods[100-A[j]].p;
					temp_weight+=goods[100-A[j]].w;
					BB[100-A[j]]=1;	//标记
				}
			}
			if(temp_weight<=AllWeight&&AllValue<temp_value)//如果比原来的价值大且合要求则赋值
			{
				AllValue=temp_value;
				Weight=temp_weight;
				temp_value=temp_weight=0;
			}
			else//为了取消不合要求时标记的
			{
				for(int kk=A[0];kk>=1;kk--)
				{
					if(A[kk])
					{		
						BB[100-A[kk]]=999;	
					}
				}
			}
		}
	}
}