问题描述
- C编写的分支限界法解01背包问题嵌入窗口界面代码问题
- 用C编写的分支限界法解01背包问题，原来无窗口界面的程序没问题，在嵌入窗口程序后得不出正解。不知代码哪出了问题。求高手修改，急用！
代码：// 123.cpp : Defines the entry point for the application.
//#include ""stdafx.h""
#include ""resource.h""#define MAX_LOADSTRING 100
HINSTANCE hInst; // current instance// Foward declarations of functions included in this code module:
LRESULT CALLBACK About(HWND UINT WPARAM LPARAM);/////////////////////////////
#define MaxSize 100 //最多结点数
int c;
char input1[MaxSize];
char input2[MaxSize];
char input3[MaxSize];
char input4[MaxSize];char output1[MaxSize];
char output2[MaxSize];
char output3[MaxSize];int v1[MaxSize];
int p = 0;
typedef struct QNode
{
int weight;
int value;
int ceng;
struct QNode *parent;
bool leftChild;}QNode*qnode; //存放每个结点
typedef struct
{qnode Q[MaxSize];
int frontrear;
}SqQueue; //存放结点的队列SqQueue sq;
int bestv=0; //最优解
int n=0; //实际物品数
int w[MaxSize]; //物品的重量
int v[MaxSize]; //物品的价值int bestx[MaxSize]; // 存放最优解
qnode bestE;
void InitQueue(SqQueue &sq ) //队列初始化
{
sq.front=1;
sq.rear=1;
}
bool QueueEmpty(SqQueue sq)
{
if(sq.front==sq.rear)
return true;
else
return false;
}void EnQueue(SqQueue &sqqnode b)//入队
{
if(sq.front==(sq.rear+1)%MaxSize)
{
// printf(""队列已满!"");
MessageBox((HWND)hInst队列已满""警告""MB_OK);
return;}
sq.Q[sq.rear]=b;
sq.rear=(sq.rear+1)%MaxSize;
}
qnode DeQueue(SqQueue &sq)//出队
{
qnode e;
if(sq.front==sq.rear)
{
//printf(""队列已空!"");
MessageBox((HWND)hInst队列已空""警告""MB_OK);
return 0;
}
e=sq.Q[sq.front];
sq.front=(sq.front+1)%MaxSize;
return e;
}
void EnQueue1(int wtint vt int i QNode *parent bool leftchild)
{
qnode b;
if (i==n) //可行叶子结点
{
if (vt==bestv)
{
bestE=parent;
bestx[n]=(leftchild)?1:0;
}
return;
}
b=(qnode)malloc(sizeof(QNode)); //非叶子结点
b->weight=wt;
b->value=vt;
b->ceng=i;
b->parent=parent;
b->leftChild=leftchild;
EnQueue(sqb);
}
void maxLoading(int w[]int v[]int c)
{
int wt=0;
int vt=0;
int i=1; //当前的扩展结点所在的
int ew=0; //扩展节点所相应的当前载重量
int ev=0; //扩展结点所相应的价值char temp1[MaxSize];char temp2[MaxSize];int q ;qnode e=NULL; qnode t=NULL; InitQueue(sq); EnQueue(sqt); //空标志进队列while (!QueueEmpty(sq)) { wt=ew+w[i]; vt=ev+v[i]; if (wt <= c) { if(vt>bestv) bestv=vt; EnQueue1(wtvtietrue); // 左儿子结点进队列} EnQueue1(eweviefalse); //右儿子总是可行；e=DeQueue(sq); // 取下一扩展结点if (e == NULL) { if (QueueEmpty(sq)) break; EnQueue(sqNULL); // 同层结点尾部标志 e=DeQueue(sq); // 取下一扩展结点 i++; } ew=e->weight; //更新当前扩展结点的值ev=e->value; }// printf(""最优价值为：%.0fnn""bestv);
itoa(bestvoutput110);
// printf(""最优s取法为：n"");
for( int j=n-1;j>0;j--) //构造最优解
{
bestx[j]=(bestE->leftChild?1:0);
bestE=bestE->parent;
}
p = 0;
q = 0;
for(int k=1;k<=n;k++)
{
if(bestx[k]==1){}
// printf(""n物品%d:重量：%.0f，价值：%.0fnn""kw[k]v[k]);
itoa(v[k]temp110);
itoa(w[k]temp210);
for(int i = 0;i<strlen(temp1);i++)
{
output2[q++] = temp1[i];
}
for(i = 0;i<strlen(temp2);i++)
{
output3[p++] = temp2[i];
}
}output2[--q] = '';output3[--p] = '';//v[] --> output2; char *;//w[] --> output3;}
////////////////////////////
// Global Variables:int APIENTRY WinMain(HINSTANCE hInstance
HINSTANCE hPrevInstance
LPSTR lpCmdLine
int nCmdShow)
{
// TODO: Place code here.
MSG msg;
// HACCEL hAccelTable;DialogBox(hInst (LPCTSTR)IDD_ABOUTBOX 0 (DLGPROC)About);return msg.wParam;}
LRESULT CALLBACK About(HWND hDlg UINT message WPARAM wParam LPARAM lParam)
{
int temp = 0;
int power = 1;
int q = 0;
switch (message)
{
case WM_INITDIALOG:
return TRUE;case WM_COMMAND: if (LOWORD(wParam) == IDCANCEL) { EndDialog(hDlg LOWORD(wParam)); return TRUE; } if(LOWORD(wParam) == IDOK) { GetDlgItemText(hDlgIDC_EDIT1input1MaxSize); n = atoi(input1); GetDlgItemText(hDlgIDC_EDIT2input2MaxSize); c = atoi(input2); GetDlgItemText(hDlgIDC_EDIT3input3MaxSize); //input3 ->> int v[]; for(int i = strlen(input3)-1;i>=0;i--) { if(input3[i] != ' ') { n += (input3[i]-'0')*power; power *= 10; } else { v1[q++] = n; n = 0; power = 1; } } v1[q++] = n; for(i = q-1;i>=0;i--) { v[p++] = v1[i]; } GetDlgItemText(hDlgIDC_EDIT4input4MaxSize); //input4 ->> int w[]; q = 0; p = 0; n = 0; power = 1; for(i = strlen(input4)-1;i>=0;i--) { if(input4[i] != ' ') { n += (input4[i]-'0')*power; power *= 10; } else { v1[q++] = n; n = 0; power = 1; } } v1[q++] = n; for(i = q-1;i>=0;i--) { w[p++] = v1[i]; } maxLoading(w v c); SetDlgItemText(hDlgIDC_EDIT5output1); SetDlgItemText(hDlgIDC_EDIT6output2); SetDlgItemText(hDlgIDC_EDIT7output3); } break;}return FALSE;}