0/1背包 回溯算法

来源：百度知道 编辑：UC知道 时间：2024/06/01 12:52:56
给定物品n件，他们的重量分别是w[0]，w[1]，……w[n-1]，物品的价值分别为v[0]，v[1]，……v[n-1]，另有一个背包，它可以容纳的总重量为w。设计一种物品挑选方案，要求从这n件物品中所选取的物品的总重量不超过背包的容量w，使选中物品的价值之和最大。
c++

#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); //按运价重