0-1背包问题:(回溯算法)
#include <iostream>
#define N 205
using namespace std;
double w[N],v[N];
double CurW=0;
double CurV=0;
double c;
double BestV=0;
int BestX[N];
int x[N];
int n;
void backtrack (int t)
{
if (t==n){
if(CurV>BestV){
BestV=CurV;
for(int i=0;i<n;i++)
BestX[i]=x[i];
}
}
else
for(int i=0;i<=1;i++){
x[t]=i;
if(i==0)
backtrack(t+1);
else if((CurW+w[t])<=c)
{
CurW+=w[t];
CurV+=v[t];
backtrack(t+1);
CurW-=w[t];
CurV-=v[t];
}
}
}
int main()
{
cout<<"物品个数和背包容量:";
cin>>n,cin>>c;
cout<<n<<"个物品的重量:";
for(int i=0;i<n;i++)
cin>>w[i];
cout<<n<<"个物品的价值:";
for(int i=0;i<n;i++)
cin>>v[i];
backtrack(0);
cout<<endl<<"背包可装最大价值:";
cout<<BestV<<endl;
cout<<"可行方案:";
for(int i=0;i<n;i++)
cout<<BestX[i]<<" ";
cout<<endl;
return 0;
}
/*
0-1背包问题:
5 10
2 2 6 5 4
6 3 5 4 6
*/