[공학]Knapsack(배낭) Problem 프로그램 - Greedy 알고리즘

소개글

- Knapsack Problem 을 해결하기위한 Greedy 알고리즘에 대한 개념 이해를 위한 코드 구현

코드 + 분석(hwp)

목차

1. 목적
2. 사용한 알고리즘
3. 구현한 알고리즘의 분석 및 예상 결과
4. 프로그램 실행 결과
5. 결론
6. 부록 - compile list ( 첨 부 )

본문내용

1. 목적
- Knapsack Problem 을 해결하기위한 Greedy 알고리즘에 대한 개념 이해를 위한 코드 구현

2. 사용한 알고리즘
- 배낭 문제의 해결을 위해 무게당 가치가 높은 물건부터 차례대로 집어 넣는 방법을 선택하였다. 물건을 나누어 넣을 수 있다는 가정 하에 이행 되었다.

3. 구현한 알고리즘의 분석 및 예상 결과
- 무게당 가치가 높은 순서로 집어넣는 방법을 사용중 6번째 배낭에 넣어지는 물건의 무게가 제한 무게를 넘어가기 때문에 넣을 수 있는 무게만큼 나누어 넣었다. 총 들어간 물건의 수는 6가지 이며, 총 들어간 무게는 제한무게를 가득 채운 15, 그리고 총 들어간 가치의 수는 55.3333 이라는 수치가 나왔다.

5. 결론
- 코드를 직접 구현해 봄으로서 배낭 문제를 해결하는 그리디 알고리즘에 대해 이해할 수 있게 되었다.

6. 부록 - compile list ( 첨 부 )
#include <stdio.h>

void knapsack(float *,float *);

float value[7] = {10, 5, 15, 7, 6, 18, 3}; // 물건의 가치
float weight[7] = {2, 3, 5, 7, 1, 4, 1}; // 물건의 무게


//-- main 함수
void main(){
knapsack(value, weight);
}

//-- 그리디 배낭 알고리즘, 무게당 가치가 가장 높은 물건을 배낭에 차례대로 넣는다.
void knapsack(float *v, float *w){
int i,j;
float tempw, weight=0;
float tempv, val=0;
int item=7, mw= 15; // 물건수, 가방 무게
float inbag[2][7];

참고 자료

없음

압축파일 내 파일목록

knapsack.cpp
knapsack.hwp