page2.cpp

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

// Page2.cpp : implementation file
//

#include "stdafx.h"
#include "hmssuanfa.h"
#include "Page2.h"
#include "ZYZZ.h"
#include <vector>
#include <algorithm>
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CPage2 property page

IMPLEMENT_DYNCREATE(CPage2, CPropertyPage)

CPage2::CPage2() : CPropertyPage(CPage2::IDD)
{
	//{{AFX_DATA_INIT(CPage2)
		SBool = true;
	m_Edit1 = 0;
	m_SZCSTIMG = _T("");
	//}}AFX_DATA_INIT
	m_psp.dwFlags &= ~(PSP_HASHELP);  //设置页二的帮助标志
}

CPage2::~CPage2()
{
}

void CPage2::DoDataExchange(CDataExchange* pDX)
{
	CPropertyPage::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CPage2)
	DDX_Text(pDX, IDC_EDIT1, m_Edit1);
	DDX_Text(pDX, IDC_EDIT2, m_SZCSTIMG);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CPage2, CPropertyPage)
	//{{AFX_MSG_MAP(CPage2)
	ON_BN_CLICKED(IDC_BTN_RUN, OnBtnRun)
	ON_WM_PAINT()
	ON_BN_CLICKED(IDC_BTN_CLEAR, OnBtnClear)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CPage2 message handlers

void CPage2::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.insert(temp);
				SetData.push_back(temp);
			}
			else
			{
             //   SetData.insert(-temp);
				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.insert(temp);
		SetData.push_back(temp);
	}
	else
	{//为负数
		//SetData.insert(-temp);
		SetData.push_back(-temp);
		SBool = true;
	}
	int n,*w,*x, j;
	int WeightC = GetDlgItemInt(IDC_EDIT1);
	n = SetData.size();
	w = new int[n+1];
	x = new int[n+1];
	sort(SetData.begin(),SetData.end());
	//把原来存入容器中的放入数组
	for (j = 1,i =1,itItem = SetData.begin();itItem != SetData.end();itItem++)
	{
		w[j++] = *itItem;
	}
	CString tempStr;
	//Loading my;
	meg = "第一艘轮船上要装的的各个货物重量为：";
	MaxLoading(w,WeightC,n,x); 
	for (i = 1; i<=n;i++)
	{
		if (x[i])
		{
			tempStr.Format("%d ,",w[i]);
			meg+=tempStr;
		}
	}
	MessageBox(meg);
	delete []w;
	delete []x;
//	CString meg;
// 	vector<int> SetData;//容器
//     vector<int>::iterator itItem;

//	CDC *myDc  = GetDC();
// 	myDc->MoveTo(70,130);
// 	myDc->LineTo(70,230);
//	myDc->LineTo(118,125);
//	myDc->SetPixel(25,25,RGB(100,100,100));
//	int C[N] = {0,4,3,2,1};
// 	int C[N] = {0,m_Edit1,m_Edit2,m_Edit3,m_Edit4,m_Edit5,m_Edit6};
// 	for (int j = 0 ; j < N; j++)
// 	{
// 		C0[j] = C[j];
// 	}
// 	int n = N - 1;
// //	int Net[N];
// 	int **size;
// 	size=(int**)new int *[N];
// 	memset(size, 0 ,sizeof(size));
// 	for(int x=0;x<N;x++) 	
//     size[x] = new int[N];
// 
// 	CMNS my;
// 	my.MNSQJ(C0,n,size);
// 	my.TraceBack(C0,size,n,Net,m);
// 	for (int i = 0; i<m; i++)
// 	{
// 		myDc->MoveTo(70+(Net[i]-1)*48,130);
// 		myDc->LineTo(70+(C[Net[i]]-1)*48,230);
// 	}
//测试之用
// 	CString meg;
// 	meg.Format("：%d ,%d,%d,%d,%d, %d",m,Net[0],Net[1],Net[2],Net[3],size[n][n]);
// 	MessageBox(meg);


// 	for(x=0;x<N;x++) 
// 		
// 		delete [] size[x];
// 	
// 	delete [] size;
// 	
// size = NULL;
}

void CPage2::OnPaint() 
{
	CPaintDC dc(this); // device context for painting
// 	CPen pen(0,1,RGB(255,100,100));
// 	dc.SelectObject(&pen);
// 	CBrush *pBrush=CBrush::FromHandle((HBRUSH)GetStockObject(NULL_BRUSH));
// 	dc.SelectObject(pBrush);
// 	// TODO: Add your message handler code here
// 	for (int i = 0; i<m; i++)
// 	{
// 		dc.MoveTo(70+(Net[i]-1)*48,130);
// 		dc.LineTo(70+(C0[Net[i]]-1)*48,230);
// 	}	
	// Do not call CPropertyPage::OnPaint() for painting messages
}

BOOL CPage2::PreTranslateMessage(MSG* pMsg) 
{
	// TODO: Add your specialized code here and/or call the base class
	switch (pMsg->message)	
	{	
	   case WM_KEYDOWN:
		{
			switch(pMsg->wParam)
        /*if (pMsg->wParam == VK_RIGHT)*/
			case VK_RIGHT:
			{
				CWnd * pCtrl = NULL; 
				pCtrl = GetFocus();	
	      	    NextDlgCtrl();
				break;
      //  GetFocus()->
	//	Perform(WM_NEXTDLGCTL,0,0);
	//	 SelectNext(ActiveControl,true,true);  
		
	//	GetNextDlgTabItem()
	//	GetNextDlgTabItem(pCtrl)->SetFocus(); 
			}
		}    
		break;
	
	}
	return CPropertyPage::PreTranslateMessage(pMsg);
}

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