arithdynamiclistview.cpp

师兄做的算法可视化演示程序

// ArithDynamicListView.cpp : implementation file
//

#include "stdafx.h"
#include "AlgorithmicDesign.h"
#include "ArithDynamicListView.h"
#include "MainFrm.h"

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

/////////////////////////////////////////////////////////////////////////////
// CArithDynamicListView

IMPLEMENT_DYNCREATE(CArithDynamicListView, CListView)

CArithDynamicListView::CArithDynamicListView()
{
	m_i = 0;
	m_y = 0;
	m_z = 0;

	vConst = "";
	vVary  = "";
	
	m_linenumber = 2;
	m_linepronumber = 2;
	memset(m_x,0,sizeof(m_x));
	m_bstop=0;
	m_odd=0;
}

CArithDynamicListView::~CArithDynamicListView()
{
}


BEGIN_MESSAGE_MAP(CArithDynamicListView, CListView)
	//{{AFX_MSG_MAP(CArithDynamicListView)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CArithDynamicListView drawing

void CArithDynamicListView::OnDraw(CDC* pDC)
{
	CDocument* pDoc = GetDocument();
	// TODO: add draw code here
}

/////////////////////////////////////////////////////////////////////////////
// CArithDynamicListView diagnostics

#ifdef _DEBUG
void CArithDynamicListView::AssertValid() const
{
	CListView::AssertValid();
}

void CArithDynamicListView::Dump(CDumpContext& dc) const
{
	CListView::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CArithDynamicListView message handlers

void CArithDynamicListView::OnInitialUpdate() 
{
	CListView::OnInitialUpdate();
	
	// TODO: Add your specialized code here and/or call the base class
	CListCtrl& theCtrl = GetListCtrl();	
	theCtrl.InsertColumn(0,"  算法  ",LVCFMT_CENTER,441);
	DWORD dwStype=GetWindowLong(theCtrl.GetSafeHwnd(),GWL_STYLE);
	dwStype&=~LVS_TYPEMASK;		//Remove the current stype flags
	dwStype|=LVS_REPORT;		//Add the List stype
	dwStype|=LVS_SHOWSELALWAYS;
	dwStype|=LVS_NOLABELWRAP;
	SetWindowLong(theCtrl.GetSafeHwnd(),GWL_STYLE,dwStype);	//Set it back into the list view

	DWORD dwStyle =  theCtrl.SendMessage(LVM_GETEXTENDEDLISTVIEWSTYLE,0,0);
	dwStyle |= LVS_EX_FULLROWSELECT ;
	theCtrl.SendMessage(LVM_SETEXTENDEDLISTVIEWSTYLE, 0, (LPARAM)dwStyle);

	DWORD dwEx =  theCtrl.GetExtendedStyle();
	theCtrl.SetExtendedStyle(dwEx|LVS_EX_FLATSB);
	SetRedraw(true);

	COLORREF	clrBk	= RGB(150, 175, 230);
	theCtrl.SetBkColor( clrBk);
    theCtrl.SetTextBkColor(clrBk);

    int m_Number;
	m_Number=theCtrl.GetItemCount();
	LV_ITEM lvi;
	lvi.mask =  LVIF_TEXT | LVIF_STATE ;
	lvi.iItem = m_Number;
	lvi.iSubItem = 0;
	lvi.pszText = (LPTSTR)(LPCTSTR)("int F( int i, int y ) ");
	lvi.stateMask = LVIS_STATEIMAGEMASK;
	lvi.state =   INDEXTOSTATEIMAGEMASK(1);
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("{/* F(i,y)表示剩余容量为y，剩余物品为i，i+1,...,n时的最优解*/");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  if( i == n-1)");
	theCtrl.InsertItem(&lvi);
	
 	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("    return ( y >= w[n-1]?p[n-1]:0 )");
	theCtrl.InsertItem(&lvi);
	
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  if( y < w[i])");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("    return F(i+1,y);");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  return(F(i+1,y)<F(i+1,y-w[i])+p[i] ? F(i+1,y-w[i]+p[i]):F(i+1,y) );");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("}");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("void X( int x[100],int y) {");
	theCtrl.InsertItem(&lvi);

	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  int z = 0;");
	theCtrl.InsertItem(&lvi);
	
	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  for( int i =0; i < n; i++) {");
	theCtrl.InsertItem(&lvi);

  	m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("    if( F(i,y-z) == F(i+1,y-z) )");
	theCtrl.InsertItem(&lvi); 

    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("      x[i] = 0;");
	theCtrl.InsertItem(&lvi); 

    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("    else");
	theCtrl.InsertItem(&lvi); 
	
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("      x[i] = 1;");
	theCtrl.InsertItem(&lvi);
	
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("    z += x[i] * w[i];");
	theCtrl.InsertItem(&lvi);
	
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("  }");
	theCtrl.InsertItem(&lvi);
	
    m_Number=theCtrl.GetItemCount();
    lvi.iItem = m_Number;
	lvi.pszText = (LPTSTR)(LPCTSTR)("}");
	theCtrl.InsertItem(&lvi);

}

//具体处理时间响应，回调函数
void CALLBACK  CArithDynamicListView::OnTimerExcute(HWND hWnd,UINT nMsg,UINT nIDEvent,DWORD dwTime)
{
    CMainFrame*	pMainFrame	=(CMainFrame*)::AfxGetMainWnd();
	CArithDynamicListView *pWnd;
	CDemoListView *pWnd1;
    pWnd = (CArithDynamicListView*)(pMainFrame->pPackDynamicFrame->p_AlgorithmiclistView);
	pWnd1 = (CDemoListView*)(pMainFrame->pPackDynamicFrame->p_DemolistView);
    if(pWnd->m_odd)//单步执行
		pWnd->OnStop();
	CListCtrl& theCtrl = pWnd->GetListCtrl();
	int state=INDEXTOSTATEIMAGEMASK(1);
    int mask=LVIF_TEXT | LVIF_STATE;
	theCtrl.SetItemState( pWnd->m_linepronumber,state, mask );
	state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
	theCtrl.SetItemState( pWnd->m_linenumber,state, mask );

    pWnd->m_linepronumber = pWnd->m_linenumber;
	
	switch(pWnd->m_linenumber)
	{
	case 2:
		{
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetI( pWnd->m_i );
			if( pWnd->m_i == pWnd->m_n - 1 )
				(pWnd->m_linenumber)++;
			else
				pWnd->m_linenumber = 4;
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetMaxValue( pWnd->vConst + pWnd->vVary );
			break;
		}
	case 3:
		{
			if( pWnd->m_y >= pWnd->m_weight[pWnd->m_n -1] )
				pWnd->vVary.Format("%d",pWnd->m_price[pWnd->m_n -1]);
			else
				pWnd->vVary = "0";
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetMaxValue( pWnd->vConst + pWnd->vVary );
			pWnd->m_linenumber = 7;//转到求解X[]
			break;
		}
	case 4:
		{
			if( pWnd->m_y < pWnd->m_weight[pWnd->m_i] )
			{
				(pWnd->m_linenumber)++;
			}
			else
			{
				pWnd->m_linenumber = 6;
			}
			break;
		}
	case 5:
		{
			pWnd->vVary.Format( "F(%d,%d)",pWnd->m_i+1,pWnd->m_y );
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetMaxValue( pWnd->vConst + pWnd->vVary );
			pWnd->m_i++;//i+1,y不变
			pWnd->m_linenumber = 2;
			break;
		}
	case 6:
		{
			if( pWnd->F(pWnd->m_i+1, pWnd->m_y) < 
				pWnd->F(pWnd->m_i+1,pWnd->m_y - pWnd->m_weight[pWnd->m_i]) + pWnd->m_price[pWnd->m_i] )
			{
				pWnd->m_y -= pWnd->m_weight[pWnd->m_i];//小，则执行后者
				CString v;
				v.Format("%d + ",pWnd->m_price[pWnd->m_i]);
				pWnd->vConst += v;
				pWnd->vVary.Format("F(%d,%d)",pWnd->m_i+1,pWnd->m_y);
				pWnd->m_i++;
			}
			else
			{
				pWnd->vVary.Format( "F(%d,%d)",pWnd->m_i+1,pWnd->m_y );
				pWnd->m_i++;//i+1,y不变
			}

			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetMaxValue( pWnd->vConst + pWnd->vVary );
			pWnd->m_linenumber = 2;
			
			break;
		}
	case 7:
		{
			pWnd->vVary.Format( "%d",pWnd->F(0,pWnd->m_totalweight) );
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetMaxValue( pWnd->vVary );
			(pWnd->m_linenumber)++;
			break;
		}
	case 8:
		{
			pWnd->m_i = 0;//进入求解X阶段，m_i重新赋值为0
			pWnd->m_y = pWnd->m_totalweight;//进入求解X阶段，m_y重新赋值为容器容量
			(pWnd->m_linenumber)++;
			break;
		}
	case 9:
		{
			pWnd->m_z = 0;
			(pWnd->m_linenumber)++;
			break;
		}
	case 10:
		{
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetI( pWnd->m_i );
			if( pWnd->m_i < pWnd->m_n )
				(pWnd->m_linenumber)++;
			else
				pWnd->m_linenumber = 16;
			break;
		}
	case 11:
		{
			if( pWnd->F(pWnd->m_i,pWnd->m_y - pWnd->m_z) == pWnd->F(pWnd->m_i+1,pWnd->m_y - pWnd->m_z) )
				(pWnd->m_linenumber)++;
			else
				pWnd->m_linenumber = 13;
			 break;
		}
	case 12:
		{
			pWnd->m_x[pWnd->m_i] = 0;
			//将m_x传给 变量显示部分
            pMainFrame->pPackDynamicFrame->p_VariablelistView->SetX( pWnd->m_i, FALSE );
			 pWnd->m_linenumber = 15;
			 break;
		}
	case 13:
		{
             (pWnd->m_linenumber)++;
			 break;
		}
	case 14:
		{
			pWnd->m_x[pWnd->m_i] = 1;
			//将m_x传给 变量显示部分
			pMainFrame->pPackDynamicFrame->p_VariablelistView->SetX( pWnd->m_i, TRUE );
			//将m_x传给 演示部分，演示部分根据其值来演示移动物体，将物体装入背包
			pMainFrame->pPackDynamicFrame->p_DemolistView->SetX( pWnd->m_i );
			pMainFrame->pPackDynamicFrame->p_DemolistView->Paint();
            (pWnd->m_linenumber)++;   
			break;
		}
	case 15:
		{
			pWnd->m_z += pWnd->m_x[pWnd->m_i] * pWnd->m_weight[pWnd->m_i];
			pWnd->m_i++;
			pWnd->m_linenumber = 10;
			break;
		}
	case 16:
		{
			(pWnd->m_linenumber)++;
			break;
		}
	default:
		{
			(pWnd->m_linenumber)++;
			break;
		}
	}
	if(pWnd->m_linepronumber == 18)
	{
		pWnd->KillTimer(nIDEvent);
        pMainFrame->pPackDynamicFrame->p_TopButtonView->m_TopbuttonDlg->OnStop();
	}
}

    
	
void CArithDynamicListView::OnExecute()
{
	SetTimer(1,1000,OnTimerExcute);
	m_bstop=0;
	m_odd=0;
}


void CArithDynamicListView::AddDemoData(int n, int m, char *p, char *w)
{

	m_i = 0;//当程序重新设置数据开始运行后，必须将m_i重新赋0，否则程序出现bug
	vConst = "";//同上
	vVary  = "";
	
	 memset(m_price,0,sizeof(m_price));
	 memset(m_weight,0,sizeof(m_weight));
     int i,flag = 1;
	 char *pdest;
	 int ch=',';
	 int k=0;
	 for(i=0;i<n-1;i++)
	 {
		 pdest = strchr(p, ch);
		 if( pdest != NULL )
		 {
			 *pdest='\0';
			 m_price[k]=atoi(p);//将字符串中的 物体重量 数值传给 m_price数组
			 k++;
			 strcpy(p,pdest+1);
		 }
	 }
	 m_price[k]=atoi(p);
	 if((k+1)!=n)
	 {
		MessageBox("    有物体没有价格!","0/1背包问题的动态规划算法",MB_OK);
		return;
	 }
	 k=0;
	 for(i=0;i<n-1;i++)
	 {
		 pdest = strchr(w, ch);
		 if( pdest != NULL )
		 {
			 *pdest='\0';
			 m_weight[k]=atoi(w);//将字符串中的 物体重量 数值传给 m_weight数组
			 k++;
			 strcpy(w,pdest+1);
		 }
	 }
	 m_weight[k]=atoi(w);
	 if((k+1)!=n)
	 {
		MessageBox("    有物体没有重量!","0/1背包问题的动态规划算法",MB_OK);
		return;
	 }
 
   m_n = n;//维数   
   m_totalweight = m;
   m_y = m_totalweight;
   vVary.Format("F(0,%d)",m_totalweight);
   
   
   CMainFrame*	pMainFrame = (CMainFrame*)::AfxGetMainWnd();
   pMainFrame->pPackDynamicFrame->p_DemolistView->AddDemoData(m_n,m_totalweight,m_price,m_weight);
   pMainFrame->pPackDynamicFrame->p_VariablelistView->SetVarianlemnpw(m_n,m_totalweight,m_price,m_weight);
   m_linenumber = 2;
   m_linepronumber = 2;
   CListCtrl& theCtrl = GetListCtrl();
   int state = LVIS_FOCUSED|LVIS_DROPHILITED|LVIS_ACTIVATING ;
   int mask =  LVIF_TEXT | LVIF_STATE;
   theCtrl.SetItemState(m_linenumber, state, mask );
   m_bstop=0;
   m_odd=0;
}

void CArithDynamicListView::SetArithmeticTimer()
{
   if(!m_bstop)
      SetTimer(1,1000,OnTimerExcute);
   m_bstop=0;
}

void CArithDynamicListView::OnStop()
{
   KillTimer(1);
   m_bstop=1;
}

void CArithDynamicListView::SetOdd()
{
     m_odd=1;
	 SetTimer(1,1000,OnTimerExcute);
	 m_bstop=0;
}



int CArithDynamicListView::F(int i, int y)
{
	if( i >= m_n )
		return 0;
	if( i == m_n-1 )
		return ( y >= m_weight[m_n-1] ? m_price[m_n-1] : 0 );
	if( y < m_weight[i] )
		return F(i+1, y);
	return ( F(i+1,y) < F(i+1,y-m_weight[i])+m_price[i] ? F(i+1,y-m_weight[i])+m_price[i] : F(i+1,y) );
}