实验五：贪心算法求解背包问题
实验内容
应用贪心算法求解离散背包问题，分析时间复杂度。
有一个承重为W的背包和n个物品，它们各自的重量和价值分别是wi和vi（1<=i<=n），设求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。
算法思想
•动态规划的思想：
–对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。
–
引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]，
ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是CH1[i] != CH2[j]，就可以计算出ch[i][j]。
算法
length(string CH1,string CH2,int b[MAX][MAX])
//用于构建动态数组
//输入：两字符窜
//输出：最长公共子序列
for(i=1;i<=ch1Len;i++)//二重循环求解
for(int j=1;j<=ch2Len;j++)
{
if(CH1[i-1]==CH2[j-1])//相等字符
{
ch[i][j]=ch[i-1][j-1]+1;
b[i][j]=0;
}
else if(ch[i-1][j]>=ch[i][j-1])//上比较大
{
ch[i][j]=ch[i-1][j];
b[i][j]=1;
}
else//左比较大
{
ch[i][j]=ch[i][j-1];
b[i][j]=-1;
}
}
printCS(int b[MAX][MAX],string x,int i,int j)
//回溯求出最长子序列输出
//输入：标记数组
//输出：最长子序列
if(i == 0 || j == 0)//边界，返回
return;
if(b[i][j] == 0)
{
printCS(b, x, i-1, j-1);//左上
cout<}
else if(b[i][j] == 1)
printCS(b, x, i-1, j);//上
else
printCS(b, x, i, j-1);//左
源程序
//应用贪心算法求解离散背包问题
#include
using namespace std;
#define MAX 100
//结构体
struct Elem
{
double W;
double V;
double P;
int number;
};
//顺序表
struct SqList
{
Elem *elem;
int length;
int listsize;
};
//构造一个空的线性顺序表
void InitList_Sq(SqList &L)
{
L.elem=(Elem *)malloc(100*sizeof(Elem));
L.length=0;
L.listsize=100;
}
//********************************
//构造背包,顺序表
//******************************
void input(SqList &L)
{
cout<<"请输入物品的个数：";
cin>>L.length;
for(int i=0;i{
cout<<"请输入第"<cin>>L.elem[i].W>>L.elem[i].V;
L.elem[i].P=L.elem[i].V/L.elem[i].W;
cout<<"价值比为："<L.elem[i].number=i+1;
}
}
//*********************************
//插入排序由大到小
//*******************************
void inser(SqList &L)
{
Elem inserter;
int index;//inserter待插入合适位置的元素,index指示插入位置
for(int pass=1;passinserter=L.elem[pass];//第pass轮时,待插入的对象是a[pass]
index=pass-1;
