算法设计_课程设计(3)

}//cp当前包内物品价值，cw当前包内物品重量 int main() { int i; bestp=0;

printf(\请输入背包最大容量:\\n\ scanf(\

printf(\请输入物品个数:\\n\ scanf(\

printf(\请依次输入物品的重量:\\n\ for(i=1;i<=n;i++) scanf(\ printf(\请依次输入物品的价值:\\n\ for(i=1;i<=n;i++) scanf(\ Backtrack(1,0,0);

printf(\最大价值为:\\n\ printf(\

printf(\被选中的物品依次是(0表示未选中，1表示选中)\\n\ for(i=1;i<=n;i++) printf(\ printf(\

3、棋盘

#include #include using namespace std;

int tile=1;int board[100][100];

void chessBoard(int tr, int tc, int dr, int dc, int size)

{ //子棋盘由原始棋盘数组board的行下标tr，列下标tc表示。用board[dr][dc]表示特殊方格 if(size==1) return; int t=tile++;

int s=size/2; //t为L型骨牌号,S分割棋盘 if(dr=tc+s) //右上棋盘 chessBoard(tr, tc+s, dr, dc, s); else { board[tr+s-1][tc+s]=t; //覆盖2号三格板 chessBoard(tr, tc+s, tr+s-1, tc+s, s); //覆盖其余部分} if(dr>=tr+s && dc

if(dr>=tr+s && dc>=tc+s) //右下棋盘 chessBoard(tr+s, tc+s, dr, dc, s); else { board[tr+s][tc+s]=t; //覆盖4号三格板 chessBoard(tr+s, tc+s, tr+s, tc+s, s);//覆盖其余棋盘} }

void main() { int size; cout<<\输入棋盘的size(大小必须是2的n次幂): \ cin>>size; int index_x,index_y; cout<<\输入特殊方格位置的坐标: \ cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;i

八、参考文献

[1]王晓东编著. 算法设计与分析[M].北京：清华大学出版社，2003年1月第1版. [2] Brian Henderson-Sellers. A Book of Object-Oriented Knowledge: An Introduction

to Object-Oriented Software Engineering[M].Prentice-Hall, 1993: 39-113