普通背包及棋盘覆盖.doc

1. 普通背包：
#include
#include
using namespace std;
struct Good
{
float p; //物品的效益
float w; //物品的重量
float X; //物品该放的数量
int flag; //物品的编号
}; //物品信息结构体

void Insertionsort(Good goods[],int n)
{
int i,j;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].p>goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}

void bag(Good goods[],float M,int n)
{
float left;
int i,j;
for(i=1;i<=n;i++)
goods[i].X=0;
left=M; //========背包剩余容量
for(i=1;ileft) //========当该物品重量大与剩余容量跳出
break;
goods[i].X=1;
left=left-goods[i].w; //=========确定背包新的剩余容量
}
if(i<=n)
goods[i].X=left/goods[i].w;//=========该物品所要放的量

for(j=2;j<=n;j++) //==========按物品编号做降序排列
{ goods[0]=goods[j];
i=j-1;
while (goods[0].flag }
goods[i+1]=goods[0];
}

cout<<"最优解为:"< int j,n;
float M;
Good *goods; //=======/定义一个指针
while(j)
{
cout<<"\t"<<"请输入物品的总种类数：";
cin>>n;
goods=new struct Good [n+1];
cout<<"\t"<<"请输入背包的最大容量：";
cin>>M;
cout<>goods[i].w;
cout<<"\t"<<"请输入第"<>goods[i].p;
goods[i].p=goods[i].p/goods[i].w; //==========得出物品的效益，重量比
cout<dl;
cin>>j;
}
}
2. 棋盘覆盖：
#include
#include
using namespace std;
int tile=1;
int board[100][100];
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
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 tc+s-1, s); //覆盖其余部分
}
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次幂): "<>size;
int index_x,index_y;
cout<<"输入特殊方格位置的坐标: "<>index_x>>index_y;
chessBoard(0,0,index_x,index_y,size);
for(int i=0;i