算法设计与分析复习题目及答案详解

分治法
1二分搜索算法利（ 分治策略）实现算法
9 实现循环赛日程表利算法（分治策略 ）
27Strassen矩阵法利（分治策略 ）实现算法
34．实现合排序利算法（分治策略 ）
实现整数法利算法（ 分治策略 ）
17．实现棋盘覆盖算法利算法（分治法 ）
29分治法求解需满足条件（子问题必须样 ）
分治法求解（01背包问题 ）

动态规划
列动态规划算法基步骤（ 构造优解 ）
列动态规划算法基素（子问题重叠性质 ）
列算法中通常底方式求解优解（动态规划法 ）
备忘录方法种算法变形（ 动态规划法 ）
长公子序列算法利算法（ 动态规划法 ）
矩阵连问题算法（动态规划算法B）设计实现
实现子段利算法（  动态规划法   ）

贪心算法
解决问题：单源短路径问题花费生成树问题背包问题活动安排问题
解决问题：N皇问题01背包问题
贪心算法基素（贪心选择性质优子结构性质）

回溯法
回溯法解旅行售货员问题时解空间树（ 排列树 ）
剪枝函数回溯法中避免效搜索采取策略
回溯法效率赖列素（ 确定解空间时间）

分支限界法
效益优先（ 分支界限法 ）搜索方式
分支限界法解团问题时活结点表组织形式（ 堆 ）
分支限界法解旅行售货员问题时活结点表组织形式（ 堆 ）
优先队列式分支限界法选取扩展结点原（ 结点优先级 ）
问题解空间树进行搜索方法中活结点次机会成活结点( 分支限界法 )
活结点表中选择扩展结点方式导致分支限界法( 栈式分支限界法 )外常见方式
（1）队列式(FIFO)分支限界法：队列先进先出（FIFO）原选取节点扩展节点
（2）优先队列式分支限界法：优先队列中规定优先级选取优先级高节点成前扩展节点

（优子结构性质）贪心算法动态规划算法点
贪心算法动态规划算法区（ 贪心选择性质   ）
回溯算法分支限界法问题解空间树会( 序树 )



14．哈弗曼编码贪心算法需计算时间（   B     ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
21面关NP问题说法正确（B ）
A NP问题解决问题
B P类问题包含NP类问题中
C NP完全问题P类问题子集
D NP类问题包含P类问题中
40背包问题贪心算法需计算时间（  B      ）
AO（n2n）     BO（nlogn）    CO（2n）      DO（n）
42．01背包问题回溯算法需计算时间（  A      ）
AO（n2n） BO（nlogn） CO（2n） DO（n）

47背包问题贪心算法需计算时间（   B     ）
AO（n2n） BO（nlogn） CO（2n） DO（n）
53．采贪心算法优装载问题计算量集装箱重量排序算法时间复杂度 ( B )
AO（n2n） BO（nlogn） CO（2n） DO（n）
56算法干条指令组成穷序列满足性质（ D ）
（1） 输入：0输入
（2） 输出：少输出
（3） 确定性：指令清晰歧义
（4） 限性：指令执行次数限执行时间限
A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)
57函数32n+10nlogn渐进表达式( B )
A 2n B 32n C nlogn D 10nlogn
59动态规划算法解决字段问题时间复杂性( B )
Alogn Bn Cn2 Dnlogn
61设f(N)g(N)定义正数集正函数果存正常数C然数N0N≥N0时f(N)≤Cg(N)称函数f(N)N充分时界g(N)记作
f(N)∈○(g(N))f(N)阶( A )g(N)阶
A高 B低C等价 D逼

二 填空题
2程序 算法  某种程序设计语言具体实现
3算法确定性指组成算法条 指令 清晰歧义
6算法指解决问题 种方法 程
7分治法般设计模式出设计出程序般 递算法
11计算算法时间复杂度通常计算 循环次数 基操作频率 计算步
14解决01背包问题动态规划回溯法分支限界法中需排序 动态规划 需排序 回溯法 分支限界法
15回溯法进行状态空间树裁剪分支时般两标准：约束条件目标函数界N皇问题01背包问题正两种类型中时约束条件目标函数界进行裁剪 01背包问题 约束条件进行裁剪 N皇问题
30回溯法种带 系统性 带 跳跃性 搜索算法
33．回溯法搜索解空间树时常两种剪枝函数 约束函数 限界函数
34计算机求解问题需时间 规模 关
35快速排序算法性取决 划分称性
36 Prim算法利 贪心 策略求解 生成树 问题时间复杂度 O(n2)
37 图m着色问题 回溯 法求解解空间树中叶子结点数 mn 解空间树中结点孩子数 m


4序列X{BCADBCD}Y{ACBABDCD}请出序列XY长公子序列 {BABCD}{CABCD}{CADCD｝
5回溯法解问题时应明确定义问题解空间问题解空间少应包含（优）解
801背包问题回溯算法需计算时间__o(n*2n)__动态规划算法需计算时间___o(min{nc2n}_
二综合题（50分）
1写出设计动态规划算法步骤
①问题具优子结构性质②构造优值递关系表达式3优值算法描述④构造优解
2 流水作业调度问题johnson算法思想
①令N1{i|aibi}②N1中作业ai非减序排序N1’N2中作业bi非增序排序N2’③N1’中作业接N2’中作业构成满足Johnson法优调度
3 n4机器M1M2加工作业i需时间分aibi(a1a2a3a4)(451210)(b1b2b3b4)(82159)求4作业优调度方案计算优值
步骤：N1{13}N2{24}
N1’{13} N2’{42}
优值：38
4 回溯法解01背包问题：n3C9V{6103}W{344}解空间长度301量组成求棵完全二叉树表示解空间（根出发左1右0）画出解空间树计算优值优解
解空间{(000)(010)(001)(100)(011)(101)
(110)(111)}
解空间树：
A
B
C
F
E
D
G
K
J
I
H
O
N
M
L
1
1
1
0
0
0
0
1
0
1
1
0
1
0

该问题优值：16 优解：（110）
5 设S｛X1X2···Xn｝严格递增序集利二叉树结点存储S中元素表示S二叉搜索树中搜索元素X返回结果两种情形（1）二叉搜索树结点中找XXi概率bi（2）二叉搜索树叶结点中确定X∈（XiXi+1）概率ai表示S二叉搜索树T中设存储元素Xi结点深度Ci叶结点（XiXi+1）结点深度di二叉搜索树T均路长p少？假设二叉搜索树T[i][j]｛XiXi+1···Xj｝优值m[i][j]W[i][j] ai1+bi+···+bj+ajm[i][j](1二叉树T均路长P+
m[i][j]W[i][j]+min{m[i][k]+m[k+1][j]} (1m[i][j]0 (i>j)
6 描述01背包问题
已知背包容量Cn件物品物品i重量Wi价值Vi求应选择装入背包中物品装入背包中物品总价值
三简答题（30分）
1流水作业调度中已知n作业机器M1M2加工作业i需时间分aibi请写出流水作业调度问题johnson法中aibi排序算法（函数名写sort(sn)）
2优二叉搜索树问题动态规划算法（设函数名binarysearchtree)）
1
void sort(flowjope s[]int n)
{
int ikjl
for(i1i {
ki
while(k if(k>n) break没ai跳出
else
{for(jk+1j if(s[j]tag0)
if(s[k]a>s[j]a) kj
swap(s[i]indexs[k]index)
swap(s[i]tags[k]tag) }
}
li记前第bi标
for(ili {
ki
for(jk+1j if(s[k]b swap(s[i]indexs[k]index) 移动indextag
swap(s[i]tags[k]tag) }
}
2
void binarysearchtree(int a[]int b[]int nint **mint **sint **w)
{
int ijktl
for(i1i { w[i][i1]a[i1]
m[i][i1]0}
for(l0lfor(i1i { ji+l
w[i][j]w[i][j1]+a[j]+b[j]
m[i][j]m[i][i1]+m[i+1][j]+w[i][j]
s[i][j]i
for(ki+1k { tm[i][k1]+m[k+1][j]+w[i][j]
if(t{ m[i][j]t
s[i][j]k
}
}
}
}
填空题（题15分题1分）
1 算法组穷 规 规定解决某特定类型问题 系列运算
2 进行问题计算复杂性分析前首先必须建立求解问题计算模型3基计算模型 机存取机RAM 机存取存储程序机RASP 图灵机
3 算法复杂性 算法效率 度量评价算法优劣重
4 计算机资源重 时间 空间 资源
5 f(n) 6×2n+n2f(n)渐进性态f(n) O(  2^n   )
6 贪心算法总做出前 选择说贪心算法整体优考虑做出选择某种意义局部优结构
二简答题（题25分题5分）
1 简单描述分治法基思想
2 简述动态规划方法运优化原理
3 谓优子结构性质？
4 简单描述回溯法基思想
5 谓PNPNPC问题
三算法填空（题20分题5分）
1n问题回溯算法
(1)二维数组A[N][N]存储皇位置第i行第j列放皇A[i][j]非0值否值0
(2)分维数组M[N]L[2*N1]R[2*N1]表示竖列左斜线右斜线否放棋子值1否值0
for(j0j if( 1 ) *安全检查*
{ A[i][j]i+1 *放皇*
2
if(iN1) 输出结果
else 3 *试探行*
4 *皇*
5
}
2数塔问题形图示数塔顶部出发结点选择左走右走起走底层求找出条路径路径值
for(rn2r>0r) 底递计算
for(c0 1 c++)
if( t[r+1][c]>t[r+1][c+1]) 2
else 3
3Hanoi算法
Hanoi(nabc)
if （n1） 1
else
{ 2
3
Hanoi(n1b a c)
}
4Dijkstra算法求单源短路径
d[u]su距离 p[u]记录前节点信息
Initsinglesource(Gs)
for each vertex v∈V[G]
do { d[v]∞ 1 }
d[s]0
Relax(uvw)
if d[v]>d[u]+w(uv)
then { d[v]d[u]+w[uv]
2
}
dijkstra(Gws)
1 Initsinglesource(Gs)
2 SΦ
3 QV[G]
4while Q<> Φ
do umin(Q)
SS∪{u}
for each vertex 3
do 4
四算法理解题（题10分）
根优先队列式分支限界法求图中v1点v9点单源短路径请画出求优解解空间树求中间舍弃结点×标记获中间解结点单圆圈○框起优解双圆圈◎框起
五算法理解题（题5分）
设n2k运动员进行循环赛现设计满足求赛日程表：
①选手必须n1名选手赛次
②选手天赛次
③循环赛短时间完成
（1）果n2k循环赛少需进行天
（2）n238时请画出循环赛日程表
六算法设计题（题15分）
分贪心算法动态规划法回溯法设计01背包问题求：说明算法策略写出算法实现步骤分析算法时间
七算法设计题（题10分）
通键盘输入高精度正整数n(n效位数≤240)掉中意s数字剩数字原左右次序组成新正整数编程定n s寻找种方案剩数字组成新数
样例输入
178543
S4
样例输出
13
二简答题（题25分题5分）
6 分治法基思想规模n问题分解k规模较子问题子问题互相独立原问题相k子问题分求解果子问题规模然够划分k子问题递进行直问题规模足够容易求出解止求出规模问题解合更规模问题解底逐步求出原问题解
7 优化原理数学化语言描述：假设解决某优化问题需次作出n决策D1D2…Dn决策序列优整数k1 < k < n前面k决策样优决策取决前面决策确定前状态决策Dk+1Dk+2…Dn优
8 某问题优解包含着子问题优解种性质称优子结构性质
9 回溯法基思想棵含问题全部解状态空间树进行深度优先搜索解叶子结点搜索程中达结点时判断该结点根子树否含问题解果确定该子树中含问题解放弃该子树搜索退回层父结点继续步深度优先搜索程回溯法中先构造出整棵状态空间树进行搜索搜索程逐步构造出状态空间树边搜索边构造
10 P(Polynomial问题)：项式复杂程度问题
NPNondeterministic Polynomial问题项式复杂程度非确定性问题
NPC(NP Complete)问题种问题解域里面穷举出答案样问题NP里面难问题种问题NPC问题
三算法填空（题20分题5分）
1n问题回溯算法
(1) M[j]&&L[i+j]&&R[ij+N]
(2) M[j]L[i+j]R[ij+N]1
(3) try(i+1MLRA)
(4) A[i][j]0
(5) M[j]L[i+j]R[ij+N]0
2数塔问题
（1）c(2)t[r][c]+t[r+1][c]
（3）t[r][c]+t[r+1][c+1]
3Hanoi算法
（1）move(ac)
（2）Hanoi(n1 a c b)
（3）Move(ac)
4（1）p[v]NIL
（2）p[v]u
(3) v∈adj[u]
（4）Relax(uvw)
四算法理解题（题10分）










1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1





五（1）8天（2分）
（2）n238时循环赛日程表（3分）
六算法设计题（题15分）
（1）贪心算法 O（nlog（n））
Ø 首先计算种物品单位重量价值ViWi然贪心选择策略单位重量价值高物品装入背包种物品全部装入背包背包物品总重量未超C选择单位重量价值次高物品装入背包策略直进行直背包装满止
Ø 具体算法描述：
void Knapsack(int nfloat Mfloat v[]float w[]float x[])
{Sort(nvw)
int i
for (i1ifloat cM
for (i1i{if (w[i]>c) break
x[i]1
cw[i]
}
if (i}
（2）动态规划法 O(nc)
m(ij)背包容量j选择物品ii+1…n时01背包问题优值01背包问题优子结构性质建立计算m(ij)递式

void KnapSack(int v[]int w[]int cint nint m[][11])
{int jMaxmin(w[n]1c)
for (j0jm[n][j]0
for (jw[n]jw[n]*
m[n][j]v[n]
for (in1i>1i)
{ int jMaxmin(w[i]1c)
for (j0j m[i][j]m[i+1][j]
for (jw[i]jw[n]*
m[i][j]max(m[i+1][j]m[i+1][jw[i]]+v[i])
}
m[1][c]m[2][c]
if(c>w[1])
m[1][c]max(m[1][c]m[2][cw[1]]+v[1])
}

（3）回溯法 O(2n)
cw前重量 cp前价值 bestp：前优值
void backtrack(int i)
回溯法  i初值1
{    if(i > n) 达叶结点
{ bestp  cp              return            }   
     if(cw + w[i] < c) 搜索左子树   
         { cw + w[i]
  cp + p[i]              
backtrack(i+1)   
           cw  w[i]
            cp  p[i]   
        }   
       if(Bound(i+1)>bestp)
搜索右子树   
        backtrack(i+1)   
 }   

七算法设计题（题10分）
逼目标选取贪心策略：步总选择剩数数字删高位低位序搜索位数字递增删数字否删第递减区间首字符然回串首述规删数字重复程s次剩数字串便问题解
具体算法：
输入s n
while（ s > 0 ）
{ i1 串首开始找
while (i < length(n)) && (n[i]{i++}
delete(ni1) 删字符串n第i字符
s
}
while (length(n)>1)&& (n[1]0’)
delete(n11) 删串首产生零
输出n
三算法填空
1背包问题贪心算法
void Knapsack(int nfloat Mfloat v[]float w[]float x[])
{
Sort(nvw)
int i
for (i1i float cM
for (i1i if (w[i]>c) break
x[i]1
c w[i]
}
if (i}
2子段 动态规划算法
int MaxSum(int n int a[])
{
int sum0 b0 sum存储前b[j] b存储b[j]
for(int j1 j if (b>0) b+ a[j]
else ba[i] 旦某区段负位置累
if(b>sum) sumb

}
return sum
}
3快速排序
template
void QuickSort (Type a[] int p int r)
{
if (p int qPartition(apr)
QuickSort (apq1) 左半段排序
QuickSort (aq+1r) 右半段排序
}
}

4排列问题
Template
void perm(Type list[] int k int m )
{ 产生[list[km]排列
if(km)
{ 剩元素
for (int i0i cout< }
else 元素排列递产生排列
for (int ik i {
swap(list[k]list[i])
perm(listk+1m)
swap(list[k]list[i])
}
}
5定已升序排序n元素a[0n1]现n元素中找出特定元素x
容易设计出二分搜索算法：
template
int BinarySearch(Type a[] const Type& x int l int r)
{
while (l int m ((l+r)2)
if (x a[m]) return m
if (x < a[m]) r m1 else l m+1
}
return 1
}
6合排序描述：
template
void Mergesort(Type a[ ] int left int right)
{
if (leftint i( left+right)2
Mergesort(a left i )
Mergesort(a i+1 right)
Merge(ab leftiright)合数组b
Copy(ab leftright ) 复制数组a
}
}

7计算xm值程
int power ( x m )
{计算xm值返回
y( 1 )im
While(i >0)
yy*x
(return y) 
}
四问答题
1计算机求解问题步骤：
1问题分析2数学模型建立3算法设计选择4算法指标5算法分析6算法实现7程序调试8结果整理文档编制
2 算法定义：
算法指解决问题时某种机械步骤定问题结果处理程
3算法三素
1操作2控制结构3数结构
13 分治法动态规划法相点：
求解问题分解成干子问题先求解子问题然子问题解原问题解
两者点：适合动态规划法求解问题分解子问题互相独立分治法求解问题分解子问题互相独立
回溯法中常见两类典型解空间树子集树排列树
22请叙述动态规划算法贪心算法异
点：需优子结构性质求优化问题
点：
动态规划：步作选择—赖子问题解
贪心方法：步作选择—赖子问题解
动态规划方法条件：子问题重叠性质
贪心方法条件：优子结构性质贪心选择性质
动态规划：底求解贪心方法： 顶求解贪心法时动态规划方法适动态规划方法时贪心法适
23 请说明动态规划方法什需优子结构性质
答：优子结构性质指问题优解包含子问题优解
动态规划方法底计算子问题优解先计算子问题优解然利子问题优解构造问题优解需优子结构
24 请说明：
(1)优先队列什数结构实现？
(2)优先队列插入算法基思想？
(3)优先队列插入算法时间复杂度？
答：（1）堆
（2）根堆中元素x插入堆末尾
然元素x关键字双亲关键字较
元素x关键字双亲关键字
元素x双亲交换然元素x新双亲关键字相直元素x关键字双亲关键字元素x根止
（3）O( log n)
26 算法复杂性分析中OΩΘ三记号意义什？忽略常数子情况
OΩΘ分提供算法运行时间什界？
答：
果存两正常数cN0N≥N0|f(N)|≤C|g(N)|记作：f(N) O(g(N))时说f(N)阶高g(N)阶
存两正常数C然数N0N ≥ N0时|f(N)|≥C|g(N)|记f(N)Ω(g(N))时说f(N)阶低g(N)阶
果存正常数c1c2n0n≥n0c1|g(N)| ≤|f(N)| ≤ c2|g(N)|
记作 f(N) (g(N)
OΩΘ分提供算法运行时间界界均
五算法设计分析题
1．动态规划策略求解长公子序列问题：
（1）出计算优值递方程
（2）定两序列X{BCDA}Y{ABCB}请采动态规划策略求出长公子序列求出程
答：1

(2)
　　　Ｙ　Ａ　Ｂ　Ｃ　Ｂ
Ｘ　　　　0　 0　 0　 0
Ｂ　　0　 0　 1　 1　 1
Ｃ　　0　 0　 1　 2　 2
Ｄ　　0　 0 1 2 2
Ａ　　0 1 1 2 2 长公子序列：｛ＢＣ｝

2．列组函数f (n) g (n)确定f (n) O (g (n)) f (n) Ω(g (n))f(n) θ(g(n))简说明理
(1) f(n)2n g(n)n
(2) f(n) g (n)log n2
(3) f(n)100 g(n)log100
(4) f(n)n3 g(n) 3n
(5) f(n)3n g(n)2n
答：
(1) f(n) O(g(n)) g(n)阶f(n)阶高
(2) f(n) Ω(g(n)) g(n)阶f(n)阶低
(3) f(n) θ(g(n)) g(n)f(n)阶
(4) f(n) O(g(n)) g(n)阶f(n)阶高
(5) f(n) Ω(g(n)) g(n)阶f(n)阶低
3．图示连通网络G克鲁斯卡尔(Kruskal)算法求G生成树T请写出算法执行程中次加入T边集TE中边说明该算法贪心策略算法基思想简分析算法时间复杂度
1
2
3
4
5
6
18
11
17
15
19
21
26
6
7
9
答：
TE{(34) (23)(15)（46）（45）}
贪心策略次连接两连通分量边中选权值边
基思想：首先图中顶点放生成树中然次连接两连通分量边中选权值边放入生成树中直生成树中n1条边
时间复杂度：O(eloge)
4 请分治策略设计递排序算法分析时间复杂性（求：分出divideconquercombine三阶段花时间基础列出递方程套公式法求出解渐进阶）
答 ： Template
void MergeSort (Type a[ ] int left int right)
{ if (left { int i（left+right）2
MergeSort（a left i）
MergeSort（a i+1 right）
Merge(a b left right)
Copy(a b left right)
}
}
Divide 阶段时间复杂性： O(1)
Conquer阶段时间复杂性： 2T(n)
Combine阶段时间复杂性： Θ(n)


套公式法：a2 b2 nlog ba n f(n)n f(n)nlog ba 阶
∴T(n) Θ(nlogn)






2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1

1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1

1 2 3 4 5 6 7









5设n2k运动员进行循环赛现设计满足求赛日程表
选手必须n1名选手赛次选手天赛次
循环赛短时间完成
(1)（4分）循环赛少需进行( n1 )天
(2)（6分）n238时请画出循环赛日程表

6考虑哈夫曼算法找字符abcdef 优编码字符出现文件中
频数 2010644416求：
（1）（4 分）简述哈夫曼算法构造优编码基步骤
（2）（5 分）构造应哈夫曼树出abcdef 种优编码
解：1）哈夫曼算法构造优编码树贪心算法基思想首先
字符应n 棵树构成森林棵树结点根权应字符频率然重复
列程n1 次：森林中根权两棵树进行合产生新树该新树根两子
树分参合两棵子树根权两子树根权
2）根题中数构造哈夫曼树图示

出 abcdef 组优编码：0100000001000011 1001
7考虑序列A[1n]中找元素问题分治算法描述：果n≤2 直接求解否序列等分成两子序列A[1n2]A[n2+1n]分找出两子序列元素x1y1 x2y2然求出A[1n]元素xmax{x1x2}元素ymin{y1y2}请出该算法计算时间T(n)满足递方程解方程确定算法时间复杂度假定n2k（k 正整数）
答：
算法时间复杂度满足递方程：
T(n)2T(n2)+2（n>2）T(2)1
n2 k（k 正整数）
T(n) T(2 k) 2T(2 k1)+2 22T(2 k2)+ 22+2
⋯
2k1T(2)+ 2k2+⋯+23+22+2
2k1+⋯+23+22+2T(n)Q(n)
8 考虑动态规划方法求解列问题：
01背包数表求：够放入背包价值物品集合

物品
i
重量 wi
价值 vi
承重量 W
1
w12
v112
W5
2
w21
v210
3
w33
v320
4
w42
v415

设： V(i j) —— 前 i 物品中够装入承重量 j 背包中总价值请递推式填写完整：
V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { } j > wi （超重）
i优子集中 i优子集中
底：行列填写表
V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0





2
0





3
0





4
0






V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0





2
0





3
0





4
0












答：
V(0 j) 0（0物品）V(i 0) 0（承重量0）
V(i j) V(i1 j) 第 i 物品装入 j < wi （超重）
V(i j) max { vi + V(i1jwj) V(i1 j) } j > wi （超重）
i优子集中 i优子集中

V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0





2
0





3
0





4
0






V
j0
1
2
3
4
5
i0
0
0
0
0
0
0
1
0
0
12
12
12
12
2
0
10
12
22
22
22
3
0
10
12
22
30
32
4
0
10
15
25
30
37







9请画出回溯法解4皇问题解空间树搜索空间树：
解空间树：










回溯法搜索空间树：


10考虑分支限界解01背包问题
定n种物品背包物品i重量wi价值vi背包容量C问应选择装入背包物品装入背包中物品总价值
示例：n3 C30 w{16 15 15} v{45 25 25}
求：1问题解空间树
2约束条件
2剪枝？
解：
问题解空间树：


约束条件：
剪枝？：
设r前尚未考虑剩余物品价值总Cv前价值bestv前优价值
r＋Cv≤bestv时剪右子树
11请画出回溯法解n301背包问题解空间树三物品重量{20 15 10}价值{20 30 25}背包容量25时搜索空间树
答：
解空间树：
1
1
1
1
1
1
0
0
0
0
0
0
0
1
1
2
3
4
5
7
8
11
12
14
15
3
10
6
9


搜索空间树：
1
行解
价值20
价值55
价值30
价值25
价值0
1
1
1
1
0
0
0
0
0
0
1
1
2

8
11
12
14
15
13
10
6
9

文档香网(httpswwwxiangdangnet)户传


《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档