bb.asm

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

;用回溯算法求解简化背包问题的算法。
STACK	EQU	1FH	;用户堆栈所在页面。
BOTTOM	EQU	00H	;用户堆栈栈底单元。
TOP	DATA	3EH	;用户堆栈栈顶指针。
OUT	EQU	20H	;输出结果存放页面。
IN	EQU	30H	;部分解存放首址。
N	EQU	8	;物品件数。
M	EQU	30	;背包载重量。
K	DATA	3FH	;有效解个数存放单元。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	SP,#5FH	;设置较大的系统堆栈。
	LCALL	SETNULL	;初始化用户堆栈。
	MOV	DPH,#OUT;初始化输出区。
	MOV	DPL,#0
	MOV	R2,#0
	CLR	A
CLROUT:	MOVX	@DPTR,A
	INC	DPTR
	DJNZ	R2,CLROUT
	MOV	R0,#IN	;初始化部分解存放区。
	MOV	R2,#N+1
CLRIN:	MOV	@R0,A
	INC	R0
	DJNZ	R2,CLRIN
	MOV	K,#0	;完整解个数初始化为零。
	MOV	A,#0	;从0号物品开始（所有物品皆为挑选对象）。
	LCALL	DPUSH
	MOV	A,#M	;从空背包开始（载重能力为M）。
	LCALL	DPUSH
	LCALL	BEIBAO	;求解背包问题。
STOP:	LJMP	STOP

WLIST:	DB	1,9,12	;物品重量表。
	DB	6,3,20
	DB	15,5

BEIBAO:	LCALL	DPOP	;背包问题求解算法。
	MOV	R2,A	;从用户堆栈中取出当前背包的剩余载重能力。
	LCALL	DPOP
	MOV	R3,A	;从用户堆栈中取出物品序号。
	MOV	DPTR,#WLIST
	MOVC	A,@A+DPTR
	MOV	R4,A	;查表得到该物品的重量。
	CLR	C
	SUBB	A,R2	;与背包的剩余载重能力相比较。
	JNZ	BB1	;不相同，另行处理。
	MOV	A,R3	;相同，将该物品放入部分解之中。
	ADD	A,#IN
	MOV	R0,A
	MOV	A,R4
	MOV	@R0,A
	MOV	DPH,#OUT;正好装满，输出一个完整解。
	MOV	A,K	;按完整解的序号计算存放地址。
	MOV	B,#N
	MUL	AB
	MOV	DPL,A
	MOV	R0,#IN	;源指针指向完整解。
	MOV	A,R3
	INC	A
	MOV	R7,A	;当前完整解的项数。
SAVE:	MOV	A,@R0	;读一个元素（对应一件物品）。
	JZ	SAVE1	;不在背包里。
	MOVX	@DPTR,A	;在背包里，输出。
	INC	DPTR
SAVE1:	INC	R0
	DJNZ	R7,SAVE
	INC	K	;完整解个数加一。
BB1:	MOV	A,R3	;当前物品是最后一件物品吗？
	INC	A
	XRL	A,#N
	JZ	BBE	;是最后一件物品，返回。
	JNC	BB2	;该物品重量超过背包的剩余载重能力。
	MOV	A,R2	;将当前背包的剩余载重能力保存起来。
	LCALL	DPUSH
	MOV	A,R3	;将当前物品序号保存起来。
	LCALL	DPUSH
	MOV	A,R3	;将该物品放入背包。
	ADD	A,#IN
	MOV	R0,A
	MOV	A,R4
	MOV	@R0,A
	MOV	A,R3	;从下一件物品开始，
	INC	A
	LCALL	DPUSH
	MOV	A,R2	;计算该物品放入背包后的剩余载重能力。
	CLR	C
	SUBB	A,R4
	LCALL	DPUSH
	LCALL	BEIBAO	;继续求解（递归调用）。
	LCALL	DPOP	;恢复当前物品序号。
	MOV	R3,A
	LCALL	DPOP
	MOV	R2,A	;恢复当前背包的剩余载重能力。
BB2:	MOV	A,R3
	ADD	A,#IN
	MOV	R0,A
	MOV	A,#0	;将该物品从背包中取出（回溯）。
	MOV	@R0,A
	MOV	A,R3
	INC	A	;从下一件物品开始，
	LCALL	DPUSH
	MOV	A,R2	;按背包当前的剩余载重能力，
	LCALL	DPUSH
	LCALL	BEIBAO	;继续求解。
BBE:	RET		;返回。

SETNULL:MOV	A,#BOTTOM	;初始化空栈，取栈底单元位置。
	MOV	TOP,A		;使栈顶指针指向栈底。
	RET			;设置好空栈。

DPUSH:	INC	TOP		;新栈顶。
	MOV	DPH,#STACK	;取堆栈所在页面。
	MOV	DPL,TOP		;取栈顶单元位置。
	MOVX	@DPTR,A		;数据压入栈顶。
	RET			;结束。

DPOP:	MOV	DPH,#STACK	;取堆栈所在页面。
	MOV	DPL,TOP		;取栈顶单元。
	MOVX	A,@DPTR		;取出栈顶元素。
	DEC	TOP		;指向新的栈顶。
	RET			;结束。
	END