page1.cpp

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

// Page1.cpp : implementation file
//

#include "stdafx.h"
#include "hmssuanfa.h"
#include "Page1.h"
#include "ANPAI.h"
#include "vector"
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CPage1 property page

IMPLEMENT_DYNCREATE(CPage1, CPropertyPage)

CPage1::CPage1() : CPropertyPage(CPage1::IDD)
{
	//{{AFX_DATA_INIT(CPage1)
	m_SZCSTIMG = _T("");
	m_BagSize = 0;
	//}}AFX_DATA_INIT
	m_psp.dwFlags &= ~(PSP_HASHELP);  //设置页一的帮助标志
//	Flag = false;
	Num = 0;
	m_TempData = 0;
	SBool = true;
//	GetDlgItem(IDC_EDIT_NUM)->SetFocus();
}

CPage1::~CPage1()
{
}

void CPage1::DoDataExchange(CDataExchange* pDX)
{
	CPropertyPage::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CPage1)
	DDX_Text(pDX, IDC_EDIT_NUM, m_SZCSTIMG);
	DDX_Text(pDX, IDC_EDIT1, m_BagSize);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CPage1, CPropertyPage)
	//{{AFX_MSG_MAP(CPage1)
	ON_BN_CLICKED(IDC_BTN_RUN, OnBtnRun)
	ON_EN_CHANGE(IDC_EDIT_NUM, OnChangeEditNum)
	ON_BN_CLICKED(IDC_BTN_CLEAR, OnBtnClear)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CPage1 message handlers

void CPage1::OnChangeEditShuzu() 
{
	
}
void CPage1::OnBtnRun() //运行
{
	// TODO: Add your control notification handler code here
    UpdateData(true);
	if (m_SZCSTIMG == "")
	{
		MessageBox("请输入数据！");
		GetDlgItem(IDC_EDIT_NUM)->SetFocus();
		return;
	}
	
	vector<int> SetData;//容器
    vector<int>::iterator itItem;
	int temp = 0;

	CString meg = "应装入的物品重量为：";
	//先把数据转化为十进制数，然后存入容器中
    for (int i = 0; i<m_SZCSTIMG.GetLength();i++)
    {
		char c = m_SZCSTIMG[i];
		//若是逗号，空格，或是回车，则为界定符。便把转换后的数据
		//存入容器中
		if (c == ','||c ==' '||c=='\n')
		{
			if (SBool)
			{
				SetData.push_back(temp);
			}
			else
			{
                SetData.push_back(-temp);
				SBool = true;
			}
			temp = 0;
		}
		//判断是否是数字
		else if (c >= '0'&&c<='9')
		{//进行十进制的转化
          temp=temp*10;
		  temp = temp+c-'0';
		}
		//判断数据的正负
		else if (c == '-')
		{
			SBool = false;
		}
    }

	if (SBool)
	{//为正数
		SetData.push_back(temp);
	}
	else
	{//为负数
		SetData.push_back(-temp);
		SBool = true;
	}
	int n,*s,*f, j;
	int *A;
	n = SetData.size();
	s = new int[n/2+1];
	f = new int[n/2+1];
	A = new int[n/2+1];
	//把原来存入容器中的放入数组
	for (j = 1,i =1,itItem = SetData.begin();itItem != SetData.end();itItem++)
	{
       s[j++] = *itItem;
	   itItem++;
	   f[i++] = *itItem;
	}
	int MaxPrice = Knapsack(s,f,m_BagSize,n/2 ,A);
// 	CANPAI my;
// 	my.GreedySelector(n/2,s,f,A);
    CString tempStr;
	for (j = 1;j<=n/2; j++)
	{
		if (A[j])
		{
			tempStr.Format("%d--",f[j]);
			meg+=tempStr;
		}
	}
	meg+="\n此时包内总价值为：";
	tempStr.Format("%d",MaxPrice);
	meg+=tempStr;
 	MessageBox(meg);
 	delete []A;//释放内存
	delete []f;
	delete []s;
}

void CPage1::OnChangeEditNum() 
{
}

void CPage1::OnBtnClear() 
{
	// TODO: Add your control notification handler code here
	m_SZCSTIMG = "";
	UpdateData(false);
	GetDlgItem(IDC_EDIT_NUM)->SetFocus();
}