twomachinesfastworkview.cpp

这是算法分析当中的一个经典问题

// TwoMachinesFastWorkView.cpp : implementation of the CTwoMachinesFastWorkView class
//

#include "stdafx.h"
#include "TwoMachinesFastWork.h"

#include "TwoMachinesFastWorkDoc.h"
#include "TwoMachinesFastWorkView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CTwoMachinesFastWorkView

IMPLEMENT_DYNCREATE(CTwoMachinesFastWorkView, CFormView)

BEGIN_MESSAGE_MAP(CTwoMachinesFastWorkView, CFormView)
	//{{AFX_MSG_MAP(CTwoMachinesFastWorkView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTwoMachinesFastWorkView construction/destruction

CTwoMachinesFastWorkView::CTwoMachinesFastWorkView()
	: CFormView(CTwoMachinesFastWorkView::IDD)
{
	//{{AFX_DATA_INIT(CTwoMachinesFastWorkView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here

}

CTwoMachinesFastWorkView::~CTwoMachinesFastWorkView()
{
}

void CTwoMachinesFastWorkView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTwoMachinesFastWorkView)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

BOOL CTwoMachinesFastWorkView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CTwoMachinesFastWorkView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CTwoMachinesFastWorkView printing

BOOL CTwoMachinesFastWorkView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CTwoMachinesFastWorkView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CTwoMachinesFastWorkView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CTwoMachinesFastWorkView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CTwoMachinesFastWorkView diagnostics

#ifdef _DEBUG
void CTwoMachinesFastWorkView::AssertValid() const
{
	CFormView::AssertValid();
}

void CTwoMachinesFastWorkView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CTwoMachinesFastWorkDoc* CTwoMachinesFastWorkView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CTwoMachinesFastWorkDoc)));
	return (CTwoMachinesFastWorkDoc*)m_pDocument;
}
#endif //_DEBUG

ThreeDimensionArray::ThreeDimensionArray(int d1,int d2,int d3)
{
    m_d1=d1;
    m_d2=d2;
    m_d3=d3;
    m_s=(char *)malloc(d1*d2*d3);
}

ThreeDimensionArray::~ThreeDimensionArray()
{
    free(m_s);
    m_s=0;
}

char * ThreeDimensionArray::GetAddress(int x,int y,int z)
{
    if (x<0 || x>=m_d1) return 0;
    if (y<0 || y>=m_d2) return 0;
    if (z<0 || z>=m_d3) return 0;
    return m_s+x*m_d2*m_d3+y*m_d3+z;
}

/////////////////////////////////////////////////////////////////////////////
// CTwoMachinesFastWorkView message handlers

int CTwoMachinesFastWorkView::GetIntArray(int a[],char * s)
{
    int i,j,State;
    BYTE c;

    j=0;
    State=0;
    for (i=0;c=s[i];i++)
    if (State==0)				// 如果等待数字
    {
	if (isdigit(c))
	{
	    a[j]=c-'0';
	    State=1;				// 等待分隔符
	}
    }
    else					// 如果等待分隔符
    {
	if (isdigit(c))				// 如果仍然是数字,就归为正在收的单元里
	{
	    a[j]=a[j]*10+(c-'0');
	}
	else					// 如果是分隔符
	{
	    j++;				// 收到的个数加1
	    State=0;				// 状态回到 0,即等待数字
	}
    }
    return (State==0) ? j : j+1;		// 返回收到的数字个数
}

int CTwoMachinesFastWorkView::FastWork(int a[],int b[],int c[],int n)
{
    int i,j,k,Sa,Sb,x,i0,j0;//int c[n+1];

    Sa=Sb=0;                             // 计算
    for (j=1;j<=n;j++)
    {
	Sa+=a[j];
	Sb+=b[j];
    }
    ThreeDimensionArray p(Sa+1,Sb+1,n+1);
    for (i=0;i<=Sa;i++)               // 赋初值
    for (j=0;j<=Sb;j++) *(p.GetAddress(i,j,1))=(a[1]<=i) | (b[1]<=j);

    for (k=2;k<=n;k++)              // 递推
    for (i=0;i<=Sa;i++)
    for (j=0;j<=Sb;j++)
    {
	*(p.GetAddress(i,j,k))=(a[k]<=i) ? *(p.GetAddress(i-a[k],j,k-1)) : 0;
	if (b[k]<=j) *(p.GetAddress(i,j,k)) |= *(p.GetAddress(i,j-b[k],k-1));
    }

    x=Sa+Sb;                // 寻找最小值
    for (i=0;i<=Sa;i++)
    for (j=0;j<=Sb;j++)
    if (*(p.GetAddress(i,j,n)))
    {
	k=max(i,j);
        if (k<x)
	{
	    x=k;
	    i0=i;
	    j0=j;
	}
    }

    for (k=n;k>=1;k--)
    {
	if (i0>=a[k] && *(p.GetAddress(i0-a[k],j0,k-1))!=0)  // k 由A机器完成
	{
	    i0-=a[k];
	    c[k]=0;
	}
	else                                                   // k 由机器B完成
	{
	    j0-=b[k];
	    c[k]=1;
	}
    }
    return x;
}


void CTwoMachinesFastWorkView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	char ss[2560];
	int  a[256];
	int  b[256];
	int  c[256];
	int  x,i,n;

	GetDlgItemText(IDC_EDIT1,ss,sizeof(ss));
	n=GetIntArray(&a[1],ss);
	GetDlgItemText(IDC_EDIT2,ss,sizeof(ss));
	if (GetIntArray(&b[1],ss)!=n)
	{
	    AfxMessageBox("Error");
	    return;
	}
	x=FastWork(a,b,c,n);
	ss[0]=0;
	sprintf(ss+strlen(ss),"IN MACHINE A:");
	for (i=1;i<=n;i++)
	if (c[i]==0)
	{
	    sprintf(ss+strlen(ss),"%d(T=%d)",i,a[i]);
	}
	strcat(ss,"\r\n");
	sprintf(ss+strlen(ss),"IN MACHINE B:");
	for (i=1;i<=n;i++)
	if (c[i]!=0)
	{
	    sprintf(ss+strlen(ss),"%d(T=%d)",i,b[i]);
	}
	sprintf(ss+strlen(ss),"\r\nTIME=%d",x);
	SetDlgItemText(IDC_EDIT3,ss);
}