没有合适的资源?快使用搜索试试~ 我知道了~
数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 139 浏览量
2021-10-02
08:07:31
上传
评论
收藏 22KB DOCX 举报
温馨提示
试读
34页
数据结构与算法专题实验实验报告_八皇后_背包问题的求解_农夫过河.docx
资源推荐
资源详情
资源评论
数据结构与算法专题实验实验报告_八皇后
_背包问题的求解_农夫过河
八皇后问题
问题描述
设在初始状态下在国际象棋的棋盘上没有任何棋子(这里
的棋子指皇后棋子)。然后挨次在第 行,第 行……第
行上布放棋子。在每一行中共有 个可选择的位置,但在
任一时刻棋盘的合法布局都必需满足 个限制条件()任
意两个棋子不得放在同一行
()任意两个棋子不得放在同一列上()任意棋子不得
放在同一正斜线和反斜线上。
基本要求
编写求解并输出此问题的一个合法布局的程序。
、实现提示:
在第 行布放棋子时,从第 列到第 列逐列考察。当在
第 行第 列布放棋子时,需要考察布放棋子后在行方向、
列方向、正斜线和反斜线方向上的布局状态是否合法,若
该棋子布放合法,再递归求解在第 行布放棋子;若该
棋子布放不合法,移去这个棋子,复原布放该棋子前的状
态,然后再摸索在第 行第 列布放棋子。
程序代码
!""记录总的棋盘状态数
#$%&""参数 代表行
%&
'
()*
""棋盘初始化,空格为+,放置皇后的地方为,
-%( !((&
'
( !""列标记初始化,表示无列冲突
-%* !**&
(* .+.
/
""主、从对角线标记初始化,表示没有冲突
-%( !((&
( ( !
$%!&
!
/
#$%&
'
*
-%* !**&
'
-%* !0
*1 !* !&""假如无冲突
'
* ..""放皇后
* ""标记,下一次该列上不能放皇后
0*1 ""标记,下一次该主对角线上不能放
皇后 * ""标记,下一次该从对角线上
不能放皇后 -%1&$%&""假如行还没有遍历完,进
入下一行
""否则输出
'
""输出棋盘状态
()*
第 种状态为:
-%( !((&
'
-%* !**&
(*
/
2%&
/
"+假如前次的皇后放置导致后面的放置无论如何都不能满
足要求,则回溯,重置+"
* .+.
* !
0*1 !
* !
/
/
/
程序结果
题目 背包问题的求解
问题描述
假设有一个能装入总体积为 3 的背包和 件体积分别为
4)4)54 的物品,能否从 件物品中选择若干件恰好
装满背包,即使 4454 3,要求找出全部满足
上述条件的解。
例如:当 3 !,各件物品的体积')))))/时,可
找到下列 组解: %)))&
%))&
%)&
%))&。
实现提示
可利用回溯法的设计思想来解决背包问题。首先,将物品
排成一列,然后,挨次选取物品装入背包,若已选取第 件
剩余33页未读,继续阅读
资源评论
lsadm1982
- 粉丝: 1
- 资源: 25万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功