bagdlg.cpp

这是用VC++编的算法分析中的实现!!有每个源程序

// BagDlg.cpp : implementation file
//

#include "stdafx.h"
#include "arithmeticdemo.h"
#include "BagDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// CBagDlg dialog


CBagDlg::CBagDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CBagDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CBagDlg)
	m_nGoodsKind = 0;
	m_nBagBulk = 0.0;
	m_nBagMaxValue = 0;
	//}}AFX_DATA_INIT
	m_BKBrush.CreateSolidBrush(RGB(171,187,222));

}


void CBagDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CBagDlg)
	DDX_Text(pDX, IDC_GOODSKIND, m_nGoodsKind);
	DDX_Text(pDX, IDC_BAGBULK, m_nBagBulk);
	DDX_Text(pDX, IDC_BAGMAXVALUE, m_nBagMaxValue);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CBagDlg, CDialog)
	//{{AFX_MSG_MAP(CBagDlg)
	ON_BN_CLICKED(IDC_CLEANBTN, OnCleanbtn)
	ON_BN_CLICKED(IDC_ANSWERBTN, OnAnswerbtn)
	ON_WM_CTLCOLOR()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBagDlg message handlers

void CBagDlg::OnCleanbtn() 
{
	// TODO: Add your control notification handler code here
	GetDlgItem(IDC_GOODSKIND)->SetWindowText("");
	GetDlgItem(IDC_EACHGOODSWEIGHT)->SetWindowText("");
	GetDlgItem(IDC_EACHGOODSVALUE)->SetWindowText("");
	GetDlgItem(IDC_BAGBULK)->SetWindowText("");
	GetDlgItem(IDC_BAGMAXVALUE)->SetWindowText("");	
}


void CBagDlg::OnAnswerbtn() 
{
	// TODO: Add your control notification handler code here
	//GetDlgItem(IDC_ANSWERBTN)->EnableWindow(FALSE);

	CStringArray weightList,valueList;
	CString strweight,strvalue;
	CQuickSortDlg qsDlg1,qsDlg2;

	UpdateData(TRUE);

	GetDlgItem(IDC_EACHGOODSWEIGHT)->GetWindowText(strweight);
	GetDlgItem(IDC_EACHGOODSVALUE)->GetWindowText(strvalue);
	qsDlg1.GetElements(strweight,m_nGoodsKind,weightList);
	qsDlg2.GetElements(strvalue,m_nGoodsKind,valueList);

	int *p,*w;
	p=new int[m_nGoodsKind+1];
	w=new int[m_nGoodsKind+1];
	p[0]=0;
	w[0]=0;

	for(int i=1;i<=m_nGoodsKind;i++)
	{
		p[i]=atoi(valueList.GetAt(i-1));
	}

	for(int j=1;j<=m_nGoodsKind;j++)
	{
		w[j]=atoi(weightList.GetAt(j-1));
	}

	
	m_nBagMaxValue=Bagsack(p,w,m_nBagBulk,m_nGoodsKind);
	CString strResult;
	strResult.Format("%d",m_nBagMaxValue);
	GetDlgItem(IDC_BAGMAXVALUE)->SetWindowText(strResult);

}

HBRUSH CBagDlg::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) 
{
	HBRUSH hbr = CDialog::OnCtlColor(pDC, pWnd, nCtlColor);
	
	// TODO: Change any attributes of the DC here
	if(nCtlColor==CTLCOLOR_DLG)
		return (HBRUSH)m_BKBrush.GetSafeHandle();
	
	// TODO: Return a different brush if the default is not desired
	return hbr;
}

int CBagDlg::Bagsack(int p[], int w[], int c, int n)
{
	int W=0;
	int P=0;
	int i=1;

    Object *Q=new Object[n];

    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;

	float f;
	for( i=0;i<n;i++)
		for(int j=i;j<n;j++)
		{
			if(Q[i].d<Q[j].d)
			{
				f=Q[i].d;
				Q[i].d=Q[j].d;
				Q[j].d=f;
			}
		
		}

       
	Bag  K;
	K.p = new int[n+1];
	K.w = new int[n+1];
	K.x = new int[n+1];
	K.bestx = new int[n+1];

	K.x[0]=0;
	K.bestx[0]=0;
	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;
	
}