알고리즘(Foundations of Algorithms, Using C++ Pseudocode 3판)5장 13번, 18번 솔루션

소개글

"알고리즘(Foundations of Algorithms, Using C++ Pseudocode 3판)5장 13번, 18번 솔루션"에 대한 내용입니다.

5-13, 5-18 풀이이며 우수숙제풀이로 선정되었던 자료입니다.
숭실대학교 김** 교수 알고리즘 과제입니다.

목차

1. 5-13 Write a backtracking algorithm for the Sum-of-Subsets problem that does not sort the weights in advance. Compare the performance of this algorithm with that of Algorithm 5.4.
2. 5-18 Use the algorithm of Exercise 17 to color the graph of Exercise 16.

본문내용

[정렬된 subset의 합을 구하는 코드의 결과]
Weight : 지금까지 합
Total : 남은 물건합
W=52
w1=2, w2=10, w3=13, w4=17, w5=22, w6=42

1) sum_of_subsets(1, 0, 106)
If (promising(1))
Return (0+106 >= 52) && (0==52 || 0+2 <= 52) : 1
If (0 == 52) : F
Else include[2]=’yes’
Sum_of_subsets(2, 2+10, 104 -10)
2) Sum_of_subsets(2, 12, 94)
If (promising(2))
Return (12+94 >= 52) && (12==52 || 12+13 <= 52) : 1

참고 자료

없음