sky67 2013-06-26 13:03 采纳率: 0%
浏览 3333

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;

}

  • 写回答

1条回答 默认 最新

  • ChatGPTᴼᴾᴱᴺᴬᴵ 2023-01-01 12:30
    关注

    看起来你的程序是在做01背包问题的分支限界法。这是一种搜索方法,在搜索时加入许多剪枝条件来减少搜索的次数,并通过比较当前的最优值来决定是否进入更低层的搜索。

    我看到你的程序中有一些问题。

    • 在函数EnQueue1()中,在比较vt与bestv的值时,应该是if (vt>bestv),而不是if (vt==bestv)。因为在分支限界法中,我们总是希望找到一个更优的解,而不是找到当前的最优解。
    • 在函数branchbound()中,当前结点出队时应该是free(b),而不是delete(b)。在C语言中,使用malloc()分配的内存空间应该使用free()来释放,而不是delete。
    • 在函数branchbound()中,在搜索下一层结点时应该将ceng加1,而不是i+1。因为ceng表示当前结点所在的层数,而i表示当前处理到的物品的编号。
    • 在函数branchbound()中,在判断当前结点是否为可行叶子结点时应该是if (i==n-1),而不是if (i==n)。因为当i==n时,表示当前已经处理完了所有的物品,此时应该将当前结点作为可行叶子结点进行处理,而不应该跳过。
    评论

报告相同问题?

悬赏问题

  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形