dialog1.cpp

非常好用的背包演示系统

// dialog1.cpp : implementation file
//

#include "stdafx.h"
#include "knap1.h"
#include "dialog1.h"
#include "tu.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// dialog1 dialog


dialog1::dialog1(CWnd* pParent /*=NULL*/)
	: CDialog(dialog1::IDD, pParent)
{
	//{{AFX_DATA_INIT(dialog1)
	
	//}}AFX_DATA_INIT
	 m_bmpBackground2.LoadBitmap(IDB_BITMAPBACKGROUND2);
	 
}


void dialog1::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(dialog1)
	DDX_Control(pDX, IDC_EDIT1, m_edit1);
	DDX_Control(pDX, IDo1, m_btnS1);
	DDX_Control(pDX, IDo4, m_btnS4);
	DDX_Control(pDX, IDo3, m_btnS3);
	DDX_Control(pDX, IDo2, m_btnS2);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(dialog1, CDialog)
	//{{AFX_MSG_MAP(dialog1)
	ON_BN_CLICKED(IDo3, Onstart)
	ON_WM_PAINT()
	ON_WM_CTLCOLOR()
	ON_BN_CLICKED(IDo1, OnPause)
	ON_BN_CLICKED(IDo2, OnContinue)
	ON_WM_CANCELMODE()
	ON_BN_CLICKED(IDo4, OnCancel)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// dialog1 message handlers
extern float  v[1000];
extern int    w[1000];
extern int    x[1000];
extern int    m_Num;
extern int    m_KnapNum;
extern CString m_strProgram;
	int account=0;
	CString str;
	CString str1;
	CString str2="";
	CString str3="";
void dialog1::Onstart() 
{
	// TODO: Add your control notification handler code here
	int i;
	CString str;
   	tu dlg;
 if(m_strProgram=="贪心算法")
	   {
	    
	   if(knap(v, w, x, m_Num,m_KnapNum))
		                 for(i=1;i<=m_Num;i++)
						 {
							str.Format("x[%d]=%d",i,x[i]);
                         	AfxMessageBox(str);

						 }
	Sleep(800);				
	dlg.DoModal();
						  
	   }
   if(m_strProgram=="动态规划")
	{
      if(Knapsack(v, w, x, m_Num,m_KnapNum))
		                 for(i=1;i<=m_Num;i++)
						 {
							str.Format("x[%d]=%d",i,x[i]);
                         	AfxMessageBox(str);

						 }   
		Sleep(800);
	   	dlg.DoModal();           
	}
  if (m_strProgram=="分支限界")
   {
	  if(Knaps(v, w, x, m_Num,m_KnapNum))
		              
  	      for(i=1;i<=m_Num;i++)
						 {
							str.Format("x[%d]=%d",i,x[i]);
                         	AfxMessageBox(str);

						 }   
      
	  Sleep(500);
	  dlg.DoModal();  
  }
}

//////////////////////////////////////////////////////////////
///////////////////////贪心算法解01背包问题///////////////////
//////////////////////////////////////////////////////////////
int dialog1::knap(float *p, int *w, int *x, int n, int cu)
{ 
    int i = 0, j = 0, index = 0, k = 0,m=0; 
    int sortResult[1000]; 
    float  mm[1000];
    for (i=1;i<=n; i++) 
    { 
        mm[i]=p[i]/w[i]; 
	} 
	for (i =1; i<=n; i++)//对映射数组赋初值0 
    { 
        sortResult[i]=0; 
    } 
    for (i=1;i<=n; i++) 
    { 
        float temp = mm[i]; 
        index = i; 
	    //找到最大的效益并保存此时的下标 
        for (j=1; j<=n; j++) 
        {            
            if ((temp < mm[j]) && (sortResult[j] == 0)) 
            { 
                temp = mm[j]; 
                index = j; 
				 
            } 
        } 
	   //对w[i]作标记排序 
        if (sortResult[index] == 0) 
        { 
            sortResult[index] = ++k; 
        } 
    } 
    //修改效益最低的sortResult[i]标记 
    for (i=1; i<=n; i++) 
    { 
        if (sortResult[i] ==0) 
        { 
            sortResult[i]=++k; 
        } 
    }
   for (i =1; i<=n; i++)//准备输出结果 
    { 
        x[i] = 0; 
    } 
   for (i=1; i<=n; i++) 
    { 
		for(j=1;j<=n;j++)
		{
			if(i==sortResult[j])//得到取物体的顺序
			{
				if (w[j] > cu)    
			 		break; 
			  	x[j] = 1;//若合适则取出 
		        ////////输出到edit1上///////////////////////
				       
		                 str.Format("物品%d ",j);
					 	 str2+=str;
		                 GetDlgItem(IDC_EDIT1)->SetWindowText(str2);
					
				///////////////////////////////////////
                cu -= w[j];//将容量相应的改变 
				if(cu<=0)
				break;
			}
			 
		}
   }
   for (i=1; i<=n; i++) 
   {
	   if(x[i]==0)
	   {
          str1.Format("物品%d  ",i);
		  str3+=str1;
	     GetDlgItem(IDC_EDIT2)->SetWindowText(str3);
	   }
	   if(x[i]==1)
         account+=p[i];
   
   }
    str.Format("总价值%d ",account);
	GetDlgItem(IDC_EDIT3)->SetWindowText(str);
   	return 1;
}
/////////////////////////////////////////////////////////////////
///////////////////////动态规划解01背包问题//////////////////////
/////////////////////////////////////////////////////////////////
int dialog1::Knapsack(float *p, int *w, int *x, int n, int m)
{
    float s=0,f[100][100];
    int i=0,y=0;
	int ymax=(w[n]-1)>m?m:(w[n]-1);
    for(y=0;y<=ymax;y++)
        f[n][y]=0;
    for(y=w[n];y<=m;y++)
        f[n][y]=p[n];
	for(i=n-1;i>1;i--)
    {   ymax=(w[i]-1)>m?m:(w[i]-1);
	    for(y=0;y<=ymax;y++)
		  f[i][y]=f[i+1][y];
     	for(y=w[i];y<=m;y++)
		  f[i][y]=(f[i+1][y]>(f[i+1][y-w[i]]+p[i]))?f[i+1][y]:(f[i+1][y-w[i]]+p[i]);
    }
    f[1][m]=f[2][m];
    if(m>=w[1])
        f[1][m]=(f[1][m]>(f[2][m-w[1]]+p[1]))?f[1][m]:(f[2][m-w[1]]+p[1]);
	  for(i=1;i<n;i++)
        if(f[i][m]==f[i+1][m])
            x[i]=0;
        else
        {
            x[i]=1;
             ////////输出到edit1上///////////////////////
				       
		                 str.Format("物品%d ",i);
					 	 str2+=str;
		               GetDlgItem(IDC_EDIT1)->SetWindowText(str2);
	 		///////////////////////////////////////
            m-=w[i];
        }
        x[n]=f[n][m]?1:0;
		if(x[n]==1)
		{
          str.Format("物品%d ",n);
		  str2+=str;
		}
    	 GetDlgItem(IDC_EDIT1)->SetWindowText(str2);
		for(i=1;i<=n;i++)
		{
			if(x[i]==0)
			{
			   str1.Format("物品%d  ",i);
		       str3+=str1;
	           GetDlgItem(IDC_EDIT2)->SetWindowText(str3);
			}
		 if(x[i]==1)
         account+=p[i];	
		}
		s=f[1][m];
       str.Format("总价值%d ",account);
	GetDlgItem(IDC_EDIT3)->SetWindowText(str);

		return 1;
}
/////////////////////////////////////////////////////////////////
///////////////////////分支限界解01背包问题题////////////////////
/////////////////////////////////////////////////////////////////
int W[1000];
float P[1000];
int cw=0;//当前重量
float cp=0.0;//当前价值
float bestp=0.0;//当前最优值
struct Object
{
	int ID;
	
	float d;
};
//////////////////上界函数//////////////////////
float dialog1::Bound(int i)
{
	
	//计算上界
	
	int cleft=m_KnapNum-cw;//剩余容量
	
	float b=cp;
	
	//以物品单位重量价值递减序装入物品
	
	while((i<=m_Num)&&(W[i]<=cleft))
		
	{
		
		cleft-=W[i];
		
		b+=P[i];
		
		i++;
		
	}
	
	//装满背包
	
	if(i<=m_Num)
		
		b+=P[i]/W[i]*cleft;
	
	return b;
}

float dialog1::Backtrack(int i)
{
	
	if(i>m_Num)
		
	{
		
		if(bestp<cp)
			
		{
			bestp=cp;
		}
		return 1.0;
	}
	
	if(cw+W[i]<=m_KnapNum) //搜索左子树
		
	{             
		
		x[i]=1;
		cw+=W[i];
    	cp+=P[i];
		Backtrack(i+1);
	    cw-=W[i];
		cp-=P[i];
	}
	
	if(Bound(i+1)>bestp)//搜索右子树
		
	{
		x[i]=0;
  		Backtrack(i+1);
	}
}

float dialog1::Knaps(float *p, int *w, int *x, int c, int n)
{  //为Knap::Backtrack初始化
	int Ww=0;
	float Pp=0.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*p[i]/w[i];
		Pp+=p[i];
		 Ww+=w[i];
	}
	if(Ww<=c)
	  return Pp;//装入所有物品
	//依物品单位重量排序
	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;
				
			}
		}
		
	for( i=1;i<=n;i++)
			
		{
			
			P[i]=p[Q[i-1].ID];
			
			W[i]=w[Q[i-1].ID];
			
		}
		 
		Backtrack(1);
		 for(i=1;i<=m_Num;i++)
		{
		   	if(x[i]==0)
			{
			   str1.Format("物品%d  ",i);
		       str3+=str1;
	           GetDlgItem(IDC_EDIT2)->SetWindowText(str3);
			}     
			  
			if(x[i]==1)
			{
			  str.Format("物品%d ",i);
			  str2+=str;
		      GetDlgItem(IDC_EDIT1)->SetWindowText(str2);
			}       
		 if(x[i]==1)
         account+=v[i];	
		 str.Format("总价值%d ",account);
	     GetDlgItem(IDC_EDIT3)->SetWindowText(str);
		}
	
			return 1;
		
}

BOOL dialog1::OnInitDialog() 
{
	CDialog::OnInitDialog();
    m_brush2.CreateSolidBrush(RGB(221,221,221));//画刷颜色
	 //按钮背景色
   	m_btnS1.SetActiveFgColor(RGB(250,0,250));
	m_btnS1.SetInactiveBgColor(RGB(221,221,221));
	m_btnS1.SetInactiveFgColor(RGB(0,0,250));
    m_btnS2.SetActiveFgColor(RGB(255,0,255));
	m_btnS2.SetInactiveBgColor(RGB(221,221,221));
	m_btnS2.SetInactiveFgColor(RGB(0,0,250));
	m_btnS3.SetActiveFgColor(RGB(250,0,250));
	m_btnS3.SetInactiveBgColor(RGB(221,221,221));
	m_btnS3.SetInactiveFgColor(RGB(0,0,250));
	m_btnS4.SetActiveFgColor(RGB(250,0,250));
	m_btnS4.SetInactiveBgColor(RGB(221,221,221));
	m_btnS4.SetInactiveFgColor(RGB(0,0,250));
  	// 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

	m_Static1.SubclassDlgItem(IDC_STATIC1,this);	
	m_Static2.SubclassDlgItem(IDC_STATIC2,this);	
	m_Static3.SubclassDlgItem(IDC_STATIC3,this);
	m_Static1.SetTextColor(RGB(0,0,255));
	m_Static2.SetTextColor(RGB(0,0,255));
	m_Static3.SetTextColor(RGB(0,0,255));
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}

void dialog1::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();
		CPaintDC dc(this);				//对话框的dc
		CDC dcMem; 
		dcMem.CreateCompatibleDC(&dc);   //创建与对话框dc兼容的内存dc

		CRect rect;
		GetClientRect(&rect);
        BITMAP bitMap;
		m_bmpBackground2.GetBitmap(&bitMap);

		CBitmap *pbmpOld=dcMem.SelectObject(&m_bmpBackground2);		//将背景位图选入内存dc中
		dc.StretchBlt(0,0,rect.Width(),rect.Height(),&dcMem,0,0,bitMap.bmWidth,bitMap.bmHeight,SRCCOPY);   //将内存dc中的位图拉伸显示在对话框的dc中
		dc.BitBlt(0,0,rect.Width(),rect.Height(),&dcMem,0,0,SRCCOPY);
 
	}
	// TODO: Add your message handler code here
	
	
	// Do not call CDialog::OnPaint() for painting messages
}

HBRUSH dialog1::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) 
{
	HBRUSH hbr = CDialog::OnCtlColor(pDC, pWnd, nCtlColor);
		if(pWnd->GetDlgCtrlID()==IDC_EDIT1)
	{
		pDC->SetTextColor(RGB(0,0,255));
		pDC->SetBkMode(TRANSPARENT);
		pDC->SetBkColor(RGB(221,221,221));
		return m_brush2;
	}
	if(pWnd->GetDlgCtrlID()==IDC_EDIT2)
	{
		pDC->SetTextColor(RGB(0,0,255));
		pDC->SetBkMode(TRANSPARENT);
		pDC->SetBkColor(RGB(255,0,255));
		return m_brush2;
	}
	if(pWnd->GetDlgCtrlID()==IDC_EDIT3)
	{
		pDC->SetTextColor(RGB(0,0,255));
		pDC->SetBkMode(TRANSPARENT);
		pDC->SetBkColor(RGB(255,0,255));
		return m_brush2;
	}
	// TODO: Change any attributes of the DC here
	
	// TODO: Return a different brush if the default is not desired
	return hbr;
}
 

void dialog1::OnPause() 
{
	// TODO: Add your control notification handler code here
	
}

void dialog1::OnContinue() 
{
	// TODO: Add your control notification handler code here
	
}

 

void dialog1::OnCancel() 
{
	// TODO: Add your control notification handler code here
		CDialog::OnCancel();
}