回溯法解背包问题实验报告.docx

Last updated at 10:00 am on 25th December 2020
回溯法解背包问题实验报告
实验4 回溯法解0-1背包问题
一 、实验要求
要求用回溯法求解0-1背包问题；
Last updated at 10:00 am on 25th December 2020
回溯法解背包问题实验报告
实验4 回溯法解0-1背包问题
一 、实验要求
要求用回溯法求解0-1背包问题；
要求交互输入背包容量，物品重量数组，物品价值数组；
要求显示结果。
二 、实验仪器和软件平台
仪器 ：带usb接口微机
软件平台：WIN-XP + VC++
三 、实验源码
#include ""
#include<iostream>
#include<cstdio>
#include<>
#include<iomanip>
using namespace std;
template<class ty>
class Knap
{
public:
friend void Init();
friend void Knapsack();
friend void Backtrack(int i);
friend float Bound(int i);
bool operator<(Knap<ty> a)const
{
if(fl< return true;
else return false;
}
private:
ty w; ;
cout<<endl;
cout<<"请依次输入"<<n<<"个物品的价值P:"<<endl;
for(i=0;i<n;i++)
cin>>bag[i].v;
for(i=0;i<n;i++)
{
bag[i].flag=0; bag[i].kk=i;
bag[i].fl=*bag[i].v/bag[i].w;
}
}
void Backtrack(int i)
{
if(i>=n) <=c) lag=1; cw+=bag[i].w;
cp+=bag[i].v; Backtrack(i+1);
cw-=bag[i].w; cp-=bag[i].v;
}
if(Bound(i+1)>bestp)lag=0; Backtrack(i+1);
}
}
<=cleft)
{
;
b+=bag[i].v;
i++;
}
/bag[i].w * cleft;
return b;
}
void Kna