2 sky67 sky67 于 2013.06.26 21:03 提问

C编写的分支限界法解01背包问题嵌入窗口界面代码问题

用C编写的分支限界法解01背包问题,原来无窗口界面的程序没问题,在嵌入窗口程序后得不出正解。不知代码哪出了问题。求高手修改,急用!CSDN移动问答
代码:// 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;

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!