알고리즘 6장 분기한정 연습문제

소개글

"알고리즘 6장 분기한정 연습문제"에 대한 내용입니다.

목차

없음

본문내용

제목 - 6장 분기한정 연습문제
1. 알고리즘 6.1(0-1 배낭 채우기 문제를 푸는 분기한정 가지치기 너비우선검색 알고리즘)을 사용하여 다음 문제 사례에 대한 이익을 최대화하시오. 알고리즘 수행 절차를 단계별로 보이시오.

W = 13

=> 알고리즘
#include<stdio.h>
#include<stdbool.h>

int W = 13;
int n = 5;
int p[6] = { 0, 20, 30, 35, 12, 3 };
int w[6] = { 0, 2, 5, 7, 3, 1 };

typedef struct
{
int level;
int profit;
int weight;
}node;

float bound(node u)
{
int j, k;
int totweight;
float result;

if (u.weight > W)
return 0;
else {
result = u.profit;
j = u.level + 1;
totweight = u.weight;
while (j <= n && totweight + w[j] <= W) {
totweight = totweight + w[j];
result = result + p[j];
j++;
}
k = j;
if (k <= n)
result = result + (W - totweight)*p[k] / w[k];
return result;

참고 자료

없음