用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 front,rear;
}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 &sq,qnode 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 wt,int 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(sq,b);
}
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(sq,t); //空标志进队列
while (!QueueEmpty(sq))
{
wt=ew+w[i];
vt=ev+v[i];
if (wt <= c)
{
if(vt>bestv)
bestv=vt;
EnQueue1(wt,vt,i,e,true); // 左儿子结点进队列
}
EnQueue1(ew,ev,i,e,false); //右儿子总是可行;
e=DeQueue(sq); // 取下一扩展结点
if (e == NULL)
{
if (QueueEmpty(sq)) break;
EnQueue(sq,NULL); // 同层结点尾部标志
e=DeQueue(sq); // 取下一扩展结点
i++;
}
ew=e->weight; //更新当前扩展结点的值
ev=e->value;
}
// printf("最优价值为:%.0f\n\n",bestv);
itoa(bestv,output1,10);
// 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,价值:%.0f\n\n",k,w[k],v[k]);
itoa(v[k],temp1,10);
itoa(w[k],temp2,10);
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] = '\0';
output3[--p] = '\0';
//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(hDlg,IDC_EDIT1,input1,MaxSize);
n = atoi(input1);
GetDlgItemText(hDlg,IDC_EDIT2,input2,MaxSize);
c = atoi(input2);
GetDlgItemText(hDlg,IDC_EDIT3,input3,MaxSize);
//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(hDlg,IDC_EDIT4,input4,MaxSize);
//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(hDlg,IDC_EDIT5,output1);
SetDlgItemText(hDlg,IDC_EDIT6,output2);
SetDlgItemText(hDlg,IDC_EDIT7,output3);
}
break;
}
return FALSE;
}