活动选择问题的实现（动态规划 和 贪心） (二)

}
部分背包问题：

上代码

[cpp]
#include
using namespace std;

const int n=10;
//定义一个结构体
typedef struct goods
{
int w;//物品的重量
int v;//物品的价值
double VbyW;

} goods;

struct selectedGood
{
int num;//选择的商品号
int residue;//最后一种商品被选择的数量，因为部分选取
};
void fastSort(goods * inputData,int n,int startLoc);
void backBag(goods* igoods,int n,int m,selectedGood* SG);


int main()
{
int W[n]={12,3,5,6,3,43,56,2,65,43};
int V[n]={4,1,7,4,65,32,4,8,3,7};
int m=30;
selectedGood SG;

//初始化
SG.num=-1;
SG.residue=0;

selectedGood* pSG=&SG;

goods igoods[n];

for(int i=0;i igoods[i].w=W[i];

for(int j=0;j igoods[j].v=V[j];

for(int k=0;k igoods[k].VbyW=(double)igoods[k].v/igoods[k].w;

fastSort(igoods,n,0);//对单位重量的价值进行排序
backBag( igoods, n, m,pSG);

cout<<"放入背包的物品："< int k;
for( k=0;knum;++k)
{
cout< }
if(pSG->residue!=0)
cout<<"最后一个物品"<< igoods[pSG->num-1].w<<"只取"<< pSG->residue;

return 0;
}

void backBag(goods* igoods,int n,int m,selectedGood* SG)
{
int tmp=0;
int residue=0;
int i;

for( i=0;i {
//tmp+=igoods[i].w;
if(tmp+igoods[i].w<=m)
{
tmp+=igoods[i].w;
}
else
{
SG->residue=m-tmp;
SG->num=i+1;
break;
}
}
if(i==n)
{
SG->num=i+1;

}


}

void fastSort(goods * inputData,int n,int startLoc)
{
if(n<2) return ;//递归停止的条件
int i=startLoc-1;//指向最后一个小于基元的数据
int j=startLoc;//移动j，挨个遍历元素
double baseDa=inputData[startLoc+n-1].VbyW;//获取基元
goods tmp;
int k=0;
while(j<=startLoc+n-1)
{
if(inputData[j].VbyW>inputData[startLoc+n-1].VbyW||j==startLoc+n-1)
{
i++;
k++;
//交换
tmp=inputData[j];
inputData[j]=inputData[i];
inputData[i]=tmp;

}
j++;
}
startLoc=i-k+1;//左边分组的位置，右边分组的位置为：i+1
fastSort(inputData,i-startLoc,startLoc);
fastSort(inputData,n-(i-startLoc)-1,i+1);


}

#include
using namespace std;

const int n=10;
//定义一个结构体
typedef struct goods
{
int w;//物品的重量
int v;//物品的价值
double VbyW;

} goods;

struct selectedGood
{
int num;//选择的商品号
int residue;//最后一种商品被选择的数量，因为部分选取
};
void fastSort(goods * inputData,int n,int startLoc);
void backBag(goods* igoods,int n,int m,selectedGood* SG);

int main()
{
int W[n]={12,3,5,6,3,43,56,2,65,43};
int V[n]={4,1,7,4,65,32,4,8,3,7};
int m=30;
selectedGood SG;

//初始化
SG.num=-1;
SG.residue=0;

selectedGood* pSG=&SG;

goods igoods[n];

for(int i=0;i igoods[i].w=W[i];

for(int j=0;j igoods[j].v=V[j];

for(int k=0;k igoods[k].VbyW=(double)igoods[k].v/igoods[k].w;

fastSort(igoods,n,0);//对单位重量的价值进行排序
backBag( igoods, n, m,pSG);

cout<<"放入背包的物品："< int k;
for( k=0;knum;++k)
{
cout< }
if(pSG->residue!=0)
cout<<"最后一个物品"<< igoods[pSG->num-1].w<<"只取"<< pSG->residue;

return 0;
}

void backBag(goods* igoods,int n,int m,selectedGood* SG)
{
int tmp=0;
int residue=0;
int i;

for( i=0;i {
//tmp+=igoods[i].w;
if(tmp+igoods[i].w<=m)
{
tmp+=igoods[i].w;
}
else
{
SG->residue=m-tmp;
SG->num=i+1;
break;
}
}
if(i==n)
{
SG->num=i+1;

}

}

void fastSort(goods * inputData,int n,int startLoc)
{
if(n<2) return ;//递归停止的条件
int i=startLoc-1;//指向最后一个小于基元的数据
int j=startLoc;//移动j，挨个遍历元素
double b