#define N 12
int w[N][N] = {
A B C D E F G H I J K L
A { 0, 205, 241, 32, 253, 27, 89, 280, 163, 189, 105, 130 },
B { 205, 0, 144, 16, 212, 133, 101, 272, 52, 295, 120, 67 },
C { 241, 144, 0, 295, 30, 156, 42, 192, 259, 224, 126, 166 },
D { 32, 16, 295, 0, 283, 180, 43, 186, 195, 180, 30, 59 },
E { 253, 212, 30, 283, 0, 162, 96, 191, 90, 168, 3, 156 },
F { 27, 133, 156, 180, 162, 0, 164, 152, 174, 207, 226, 235 },
G { 89, 101, 42, 43, 96, 164, 0, 55, 160, 86, 158, 200 },
H { 280, 272, 192, 186, 191, 152, 55, 0, 114, 249, 292, 8 },
I { 163, 52, 259, 195, 90, 174, 160, 114, 0, 295, 241, 246 },
J { 189, 295, 224, 180, 168, 207, 86, 249, 295, 0, 209, 234 },
K { 105, 120, 126, 30, 3, 226, 158, 292, 241, 209, 0, 37 },
L { 130, 67, 166, 59, 156, 235, 200, 8, 246, 234, 37, 0 }
};
| $B2]Bj(B5.1/5.2$BN>MQ(B SAMPLE_12
|
#define N 12
int w[N][N] = {
{ 0, 122, 73, 54, 50, 140, 130, 100, 36, 85, 139, 73 },
{ 122, 0, 50, 70, 108, 28, 14, 89, 100, 100, 32, 166 },
{ 73, 50, 0, 20, 72, 73, 61, 81, 51, 81, 67, 127 },
{ 54, 70, 20, 0, 63, 92, 81, 85, 32, 81, 85, 114 },
{ 50, 108, 72, 63, 0, 117, 112, 54, 71, 36, 135, 58 },
{ 140, 28, 73, 92, 117, 0, 14, 85, 124, 100, 51, 175 },
{ 130, 14, 61, 81, 112, 14, 0, 86, 112, 99, 40, 170 },
{ 100, 89, 81, 85, 54, 85, 86, 0, 108, 20, 121, 100 },
{ 36, 100, 51, 32, 71, 124, 112, 108, 0, 98, 112, 108 },
{ 85, 100, 81, 81, 36, 100, 99, 20, 98, 0, 130, 81 },
{ 139, 32, 67, 85, 135, 51, 40, 121, 112, 130, 0, 192 },
{ 73, 166, 127, 114, 58, 175, 170, 100, 108, 81, 192, 0 }
};
|
| $B2]Bj(B5.1/5.2$BN>MQ(B SAMPLE_13
|
#define N 13
int w[N][N] = {
{ 0, 120, 136, 91, 22, 32, 42, 104, 110, 108, 128, 120, 81 },
{ 120, 0, 91, 36, 130, 136, 98, 127, 10, 197, 92, 89, 100 },
{ 136, 91, 0, 73, 156, 130, 94, 197, 90, 240, 10, 173, 166 },
{ 91, 36, 73, 0, 104, 102, 63, 125, 28, 180, 71, 100, 94 },
{ 22, 130, 156, 104, 0, 50, 64, 89, 120, 86, 149, 114, 71 },
{ 32, 136, 130, 102, 50, 0, 40, 136, 126, 130, 121, 150, 112 },
{ 42, 98, 94, 63, 64, 40, 0, 130, 89, 150, 86, 130, 100 },
{ 104, 127, 197, 125, 89, 136, 130, 0, 120, 91, 193, 51, 32 },
{ 110, 10, 90, 28, 120, 126, 89, 120, 0, 188, 91, 85, 92 },
{ 108, 197, 240, 180, 86, 130, 150, 91, 188, 0, 233, 140, 102 },
{ 128, 92, 10, 71, 149, 121, 86, 193, 91, 233, 0, 171, 162 },
{ 120, 89, 173, 100, 114, 150, 130, 51, 85, 140, 171, 0, 45 },
{ 81, 100, 166, 94, 71, 112, 100, 32, 92, 102, 162, 45, 0 }
};
|
| $B2]Bj(B5.1/5.2$BN>MQ(B SAMPLE_14
|
#define N 14
int w[N][N] = {
{ 0, 73, 156, 130, 94, 197, 90, 240, 10, 173, 166, 175, 227, 234 },
{ 73, 0, 104, 102, 63, 125, 28, 180, 71, 100, 94, 140, 170, 170 },
{ 156, 104, 0, 50, 64, 89, 120, 86, 149, 114, 71, 50, 71, 85 },
{ 130, 102, 50, 0, 40, 136, 126, 130, 121, 150, 112, 45, 112, 133 },
{ 94, 63, 64, 40, 0, 130, 89, 150, 86, 130, 100, 82, 135, 148 },
{ 197, 125, 89, 136, 130, 0, 120, 91, 193, 51, 32, 136, 95, 70 },
{ 90, 28, 120, 126, 89, 120, 0, 188, 91, 85, 92, 161, 180, 175 },
{ 240, 180, 86, 130, 150, 91, 188, 0, 233, 140, 102, 100, 20, 22 },
{ 10, 71, 149, 121, 86, 193, 91, 233, 0, 171, 162, 166, 219, 228 },
{ 173, 100, 114, 150, 130, 51, 85, 140, 171, 0, 45, 164, 141, 120 },
{ 166, 94, 71, 112, 100, 32, 92, 102, 162, 45, 0, 120, 100, 85 },
{ 175, 140, 50, 45, 82, 136, 161, 100, 166, 164, 120, 0, 81, 110 },
{ 227, 170, 71, 112, 135, 95, 180, 20, 219, 141, 100, 81, 0, 36 },
{ 234, 170, 85, 133, 148, 70, 175, 22, 228, 120, 85, 110, 36, 0 }
};
|
| $B2]Bj(B5.1/5.2$BN>MQ(B SAMPLE_15
|
#define N 15
int w[N][N] = {
{ 0, 50, 64, 89, 120, 86, 149, 114, 71, 50, 71, 85, 22, 73, 86 },
{ 50, 0, 40, 136, 126, 130, 121, 150, 112, 45, 112, 133, 63, 76, 54 },
{ 64, 40, 0, 130, 89, 150, 86, 130, 100, 82, 135, 148, 63, 42, 92 },
{ 89, 136, 130, 0, 120, 91, 193, 51, 32, 136, 95, 70, 73, 104, 175 },
{ 120, 126, 89, 120, 0, 188, 91, 85, 92, 161, 180, 175, 102, 51, 180 },
{ 86, 130, 150, 91, 188, 0, 233, 140, 102, 100, 20, 22, 92, 150, 140 },
{ 149, 121, 86, 193, 91, 233, 0, 171, 162, 166, 219, 228, 142, 89, 163 },
{ 114, 150, 130, 51, 85, 140, 171, 0, 45, 164, 141, 120, 92, 92, 198 },
{ 71, 112, 100, 32, 92, 102, 162, 45, 0, 120, 100, 85, 50, 73, 156 },
{ 50, 45, 82, 136, 161, 100, 166, 164, 120, 0, 81, 110, 72, 110, 41 },
{ 71, 112, 135, 95, 180, 20, 219, 141, 100, 81, 0, 36, 81, 139, 120 },
{ 85, 133, 148, 70, 175, 22, 228, 120, 85, 110, 36, 0, 86, 141, 151 },
{ 22, 63, 63, 73, 102, 92, 142, 92, 50, 72, 81, 86, 0, 58, 106 },
{ 73, 76, 42, 104, 51, 150, 89, 92, 73, 110, 139, 141, 58, 0, 130 },
{ 86, 54, 92, 175, 180, 140, 163, 198, 156, 41, 120, 151, 106, 130, 0 }
};
|
$B;n83(B
$B
$B9pCN(B
$B2]Bj$=$N$b$N$KD>@\$*Ez$($O$G$-$^$;$s$,!"2]BjDs=P$K4X$o$k#C8@8l(B
$B$N%W%m%0%i%_%s%0AjCL$r!"ITDj4|$J$,$i3+:E$7$^$9!#(BTA$B$,AjCL$K$N$j$^$9!#(B
$B;~4V8BDj$G$9$N$GCm0U$7$F$/$@$5$$!#(B
$B4uK>:j(B(tanishi)$B!";3K\(B(haruyosh)$B!"55ED(B(kameda)$B$K(B
@image.esys.tsukuba.ac.jp$B$r$D$1$F2<$5$$!K$r$*4j$$$7$^$9!#(B
- 2004/4/22(Thu), 17:00-18:00
$B!!!!>l=j!'(B3L302$B!JI,MW$,$"$l$P(B5L502$B$K0\F0$9$k$3$H$b$"$j$^$9!K(B
$B!!!!#T#A!'@>:j!JM}9)3X8&5f2J#1G/!KC4EvM=Dj(B
- 2004/4/23(Fri), 16:30-18:00
$B!!!!>l=j!'(B3L302$B!JI,MW$,$"$l$P(B5L502$B$K0\F0$9$k$3$H$b$"$j$^$9!K(B
$B!!!!#T#A!';3K\!J%7%9%F%`>pJs3X8&5f2J#1G/!KC4EvM=Dj(B
2004/08/16$B8=:_!#(B
$B2JL\HV9f(B/$BCNE*9)3X(B 3206/S513111
$B2JL\HV9f(B/$B5!G=9)3X(B 3240/S613111
$B1QL>(B Data Structure and Algorithm
$BC4Ev6541(B $B55EDG=@.(B
$B8&5f<<(B 3M304
$BEEOC(B 5256
Office Hour Weekday 10:00-18:00
e-mail [email protected]
$B4XO"2JL\(B $B7W;;5!=xO@(BII(S511024/S611024)
$B%W%m%0%i%_%s%0=xO@(B(S511034/S611034)
$B%0%i%UM}O@(B(S512041/S612041)
$Bhttp://www.kameda-lab.org/lecture/course-a-j.html
$B!|4XO">pJs!'(B
$BF1L>$NCNE*9)3XG[Ev2JL\$H5!G=9)3XG[Ev2JL\$OF10l$l$NLdBj$K9g$o$;$F!"(B
$B%W%m%0%i%_%s%0>e$GLdBj$r$I$N$h$&$KI=$9$Y$-$+!"pJs=hM}G=NO$HO@M}E*!&(B
$B?t3XE*;W9M!&2r@OG=NO$r=,F@$7$F$b$i$&!#(B
$B!|;HMQ652J=q!";29M=q!'(B
$B652J=q$O;HMQ$7$J$$!#;29M=q$H$7$F$O2<5-$N$b$N$r5s$2$F$*$/!#(B
$B!}%"%k%4%j%:%`$H%G!<%?9=B$!=2~D{(BC$B8@8lHG!JEE5$9)3XF~Lg%7%j!<%:!K(B
$BJ?EDIYIW(B($BCx(B)$B?9KL=PHG(B(2002/09),ISBN:462772652X / 2,200$B1_(B
$B!}%"%k%4%j%:%`%$%s%H%m%@%/%7%g%s!JA4;04,!K(B
Thomas H. Cormen $BB>(B($B86Cx(B),$B@uLnE/IW(B $BB>(B($BK]Lu(B),$B6aBe2J3X(B($BK]Lu(B),$B6aBe2J3X
$B!|C10L2A4p=`!'(B
$B$[$\3V=5$G%l%]!<%H2]Bj$r=P$9!#:GDc(B6$B3d0J>eDs=P$9$k$3$H!#(B
$B!:@Z$r2a$.$?Ds=P$KBP$7$F$O!"FbMF$,NI$/$H$bI>E@$OH>J,$7$+M?$($J$$!#(B
$B@.@SI>2A$O86B'$H$7$F%l%]!<%H$N$_$G9T$$!"%l%]!<%H2]Bj$NI>E@Am7W$,(B6$B3d0J>e$G9g3J!J(B60%$B0J>e(B70%$BL$K~$r(BC$BI>2A!"(B70%$B0J>e(B80%$BL$K~$r(BB$BI>2A!"(B80%$B0J>e$r(BA$BI>2A!K$H$9$k!#(B
60%$BL$K~$O(BD$BI>2A$H$7$FC10L$OG'Dj$7$J$$!#%l%]!<%H2]Bj$NI>2AeDs=P$9$k$3$H!#(B
$B!:@Z$r2a$.$?Ds=P$KBP$7$F$O!"FbMF$,NI$/$H$bI>E@$OH>J,$7$+M?$($J$$!#(B
$B@.@SI>2A$O86B'$H$7$F%l%]!<%H$N$_$G9T$&!#(B
$B%l%]!<%H2]Bj$NI>E@Am7W$,(B6$B3d0J>e$G9g3J$H$9$k!#(B
60%$B0J>e(B70%$BL$K~$r(BC$BI>2A!"(B
70%$B0J>e(B80%$BL$K~$r(BB$BI>2A!"(B
80%$B0J>e$r(BA$BI>2A$H$9$k!#(B
60%$BL$K~$O(BD$BI>2A$H$7$FC10L$OG'Dj$7$J$$!#(B
$B%l%]!<%H2]Bj$NI>2A
$B!|$`$3$H!'(B
$B%3%s%T%e!<%?$,$$$/$i9bB.$K$J$C$F$b!"0MA3$H$7$F2r$1$J$$LdBj$O?tB?$/$"$k$3$H$H!"8=e2A(B
$B$$$m$$$m$J%"%k%4%j%:%`!?CV$-49$(!&6a;w(B
$B!!LdBj$NCV49!&JQ49(B
$B!!!!!!(BKnapsack=$B:GD97PO)LdBj(B
$B!!lEM_K!(B
$B!!!!!!(BFractional Knapsack
$B!!!!!!(BKnapsack by Fully polynomial time approximation
$B!!=d2s%;!<%k%9%^%sLdBj(B
$B!!!!!!:GE,2r(B
$B!!!!!!Fs6a;w%"%k%4%j%:%`(B
$B!Z(B
$B#2#0#0#4G/EY%7%i%P%9$N%3%T!<(B(PDF)$B![(B
<[email protected]>
|