수다닷컴

질문 제목 :동적 할당을 할 때 에러가 생겨요 ㅠ.ㅠ0-1knapsack problem을 branch and bound(분기한정법)을이용해서 해결하는 과제에용:)
(각 아이템에 weight과 benefit이 주어졌을 때 제한된 포대자루에 아이템을 어떻게 넣어야 최고 수익을 얻을 수 있을지에 대한 문제입니다)
저는 linked list를 이용해서 트리형태로 구현하려고 해서
각 node가 왼쪽을 가리키는 포인터와 오른쪽을 가리키는 포인터를 있게 했고,
점점 가지가 뻗쳐나갈 때마다 동적으로 메모리를 할당하게 했고
promising한 node들을 point하는 linked list를 추가로 두어서
그 promising linked list를 보고 가지를 뻗쳐 나가게 하려고 했는데가지가 한번 밑으로 뻗어나가고 나서
(동적 할당으로)
두번째로 뻗어 나가려고 할때 오류가 나요 ㅠㅠㅠㅠㅠ전체 코드 첨부하고
또 그림으로 설명한 사진 파일도 첨부합니다 ㅠㅠㅠㅠ
제발 제발 꼭 도와주세요 ㅠㅠㅠ
축젠데 2틀째 과제하면서 밤을 새고 있어요 ㅠㅠㅠ

질문 내용 :
a는 item의 개수이며
weightbound는 포대가 실을 수 있는 무게입니다.int branchandbound(int a, int weightbound)
{
int max_benefit;
int item=0;
int i,j;
bnb *node, *root;
promising *promisingcur, *rootofpromising, *biggestbound, *check, *temp;

/*promising한 node를 point하고 있는 linked list를 만든다 (struct bnb에서 right변수 사용)*/
rootofpromising = (promising *)malloc(sizeof(promising));

promisingcur = rootofpromising;

biggestbound = (promising *)malloc(sizeof(promising));

/*initialize first node of the branch and bound tree*/
root = (bnb *)malloc(sizeof(bnb));
node = root;
ce:pre node-benefit = 0;
node-weight = 0;
node-itemno = 0;
node-promising = 1;
node-bound = getbound(a, node-benefit, node-weight, weightbound, node-itemno);
node-right = node-left = null;
node-up = null; /*promising linked list의 다음 node 메모리를 할당해주고 root node를 추가시킨다*/
temp = promisingcur;
promisingcur-next = (promising *)malloc(sizeof(promising));
promisingcur = promisingcur-next;
promisingcur-bnbnode = node;
promisingcur-next = null;
promisingcur-back = temp;

/*왼쪽과 오른쪽 node로 extend 시킨다*/
extend(a, weightbound, node, &max_benefit, promisingcur); check = rootofpromising-next;
while(rootofpromising-next != null)
{
/*promising linked list에서 node가 한개면 그 node를 extend함*/
if(check-next == null)
biggestbound-bnbnode = check-bnbnode;
/*두개 이상이면 계속해서 비교를 해서 가장 bound가 큰 node를 extend함*/
else
{
while(check-next != null)
{
if((check-next-bnbnode-bound) (check-bnbnode-bound))
{
biggestbound-bnbnode = check-next-bnbnode;
}
check = check-next;
}
}
//extend(a, weightbound, biggestbound-bnbnode, &max_benefit, promisingcur);
biggestbound-bnbnode-right = (bnb *)malloc(sizeof(bnb));
biggestbound-bnbnode-left = (bnb *)malloc(sizeof(bnb));

*
이 지점에서 에러가 납니다.
extend함수에서 어떤 노드에 동적으로 메모리를 할당하려고 할 때런타임 에러로
unhandled exception at 0x77d215de in algorithmhomework.exe: 0xc0000005: access violation writing location 0xcdcdcde5.
라고 뜹니다 ㅠ.ㅠ }
}void extend(int a, int weightbound, bnb *node, int *max_benefit, promising *promisingcur)
{
bnb *rnode, *lnode;
promising *temp;
node-right = (bnb *)malloc(sizeof(bnb));
node-left = (bnb *)malloc(sizeof(bnb));
lnode = node-left;
rnode = node-right;

/*put values for the left node*/
/*parent node에서 item의 benefit과 weight을 더한다*/
lnode-benefit = node-benefit + inputvalue[0].benefit;
lnode-weight = node-weight + inputvalue[0].weight;
lnode-itemno = node-itemno + 1;
pr/spanprintf(lnode\tbenefit:%d\tweight:%d\titem:%d\n,lnode-benefit,lnode-weight,lnode-itemno);
/*bound는 greedy함수를 조금 변형시킨 함수를 사용한다*/
lnode-bound = getbound(a, lnode-benefit, lnode-weight, weightbound, lnode-itemno); /*이 node의 benefit이 max benefit보다 크면 max_benefit을 이 benefit 값으로 바꾼다(단 이 item을 넣은 weight이 knapsack weight을 넘지 않을 때)*/ if(lnode-benefit *max_benefit && lnode-weight = weightbound)
*max_benefit = lnode-benefit;
/*만약 bound가 max_benefit보다 작거나 weight이 knapsack weight을 넘으면node를 nonpromising으로 지정해준다 (promising을 0으로 설정)*/ if(lnode-bound *max_benefit || lnode-weight weightbound)
{
lnode-promising= 0;
lnode-left = null;
lnode-right = null;
}
/*promising인 경우 왼쪽과 오른쪽 node 메모리를 할당해주고 promisingnodes linked list에 추가해준다*/
else
{
lnode-promising = 1;
lnode-up = node;
lnode-right = (bnb *)malloc(sizeof(bnb));
lnode-left = (bnb *)malloc(sizeof(bnb));
lnode-right-right = lnode-right-left = lnode-left-right = lnode-left-left = null;

temp = promisingcur;
promisingcur-next = (promising *)malloc(sizeof(promising));
promisingcur = promisingcur-next;
promisingcur-bnbnode = lnode;
promisingcur-next = null;
promisingcur-back = temp;
} /*put values for the right node (do the same as the left side)*/ rnode-benefit = node-benefit;
rnode-weight = node-weight;
rnode-itemno = node-itemno + 1;
printf(rnode\tbenefit:%d\tweight:%d\titem:%d\n,rnode-benefit,rnode-weight,rnode-itemno);
rnode-bound = getbound(a, rnode-benefit, rnode-weight, weightbound, rnode-itemno);
if(rnode-benefit *max_benefit && rnode-weight = weightbound)
*max_benefit = rnode-benefit;
if(rnode-bound *max_benefit || rnode-weight weightbound)
{
rnode-promising= 0;
rnode-right = null;
rnode-left = null;
}
else
{
rnode-promising= 1;
rnode-up = node;
rnode-right = (bnb *)malloc(sizeof(bnb));
rnode-left = (bnb *)malloc(sizeof(bnb));
rnode-right-right = rnode-right-left = rnode-left-right = rnode-left-left = null; temp = promisingcur;
promisingcur-next = (promising *)malloc(sizeof(promising));
promisingcur = promisingcur-next;
promisingcur-bnbnode = rnode;
promisingcur-next = null;
promisingcur-back = temp;
} //자녀가 둘다 promising이라면 부모 node를 promising linked list에서 delete(더이상 부모에서부터 extend하지 않을 테니까) if(lnode-promising==1 && rnode-promising==1)
{
temp = promisingcur-back-back;
promisingcur-back-back-back-next = promisingcur-back;
promisingcur-back = promisingcur-back-back;
free(temp);
}
}

신청하기