普通背包及棋盘覆盖.doc

1. 普通背包：
#include <iostream.h>
#include <string>
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;i<n;i++)
{ if(goods[i].w>left) //========当该物品重量大与剩余容量跳出
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].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}

cout<<"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}

void main()
{
int j,n;
float M;
Good *goods; //=======/定义一个指针
while(j)
{
cout<<"\t"<<"请输入物品的总种类数：";
cin>>n;
goods=new struct Good [n+1];
cout<<"\t"<<"请输入背包的最大容量：";
cin>>M;
cout<<endl;
int i;

for(i=1;i<=n;i++)
{ goods[i].flag=i;
cout<<"\t"<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"\t"<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w; //==========得出物品的效益，重量比
cout<<endl;

}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press [1] to run agian"<<endl;
cout<<"press [0] to exit"<<endl;
cin>>j;
}
}
2. 棋盘覆盖：
#include<iostream>
#include<stdlib.h>
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<tr+s && dc<tc+s) //残缺方格位于左上棋盘
chessBoard(tr, tc, dr, dc, s);
else {
board[tr+s-1][tc+s-1]=t;/ //覆盖1号三格板
chessBoard(tr, tc, tr+s-1, tc+s-1, s); //覆盖其余部分
}
if(dr<tr+s && dc>=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) //残缺方格位于左下棋盘
chessBoard(tr+s, tc, dr, dc, s);
else
{
board[tr+s][tc+s-1]=t; //覆盖3号三格板
chessBoard(tr+s, tc, tr+s, 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次幂): "<<endl;
cin>>size;
int index_x,index_y;
cout<<"输入特殊方格位置的坐标: "<<endl;
cin>>index_x>>index_y;
chessBoard(0,0,index_x,index_y,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
cout<<board[i][j]<<"\t";
cout<<endl;
}
}