C++求正确的背包问题的回溯程序!!

来源:百度知道 编辑:UC知道 时间:2024/05/22 04:04:44

#include<fstream>
using namespace std;
struct bag{
double w;
double p;
double p_w;
int order;
}; //说明物品特性

void sort(struct bag *a,int low,int high);

int main()
{
int n,i;
double *x; //解向量,由于书数组,拿指针表示
double m,cost=0;
struct bag *b; //结构数组,用于表示所有物品

//定义文件流并与具体的磁盘文件相关联
ifstream fin;
fin.open("背包问题_in.txt");

ofstream fout;
fout.open("背包问题_out.txt");

//输入物品数目 n 背包容量 M
fin>>n>>m;

//动态分配存储空间
b=new struct bag[n];
x=new double[n];

for(i=0;i<n;i++){
fin>>b[i].w>>b[i].p; //输入物品重量和运价
b[i].p_w=b[i].p/b[i].w; //求出运价重量比
b[i].order=i; //贴标签
}

sort(b,0,n-1); //按运价重量比从大到小进行排序

for(i=0;i<n;i++)
x[i]=0; //初始化解向量

for(i=0;i<n;i++) //处理所有物品
if(b[i].w<=m){ //若背包能放得下整个物品
x[b[i].order]=1; //放入背包
m-=b[i].w; //背包剩