马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<iostream>
using namespace std;
int n;//物品个数
int BackpackVolume;//背包容量
int maxValue;//最大价值
int *weight = new int[n];//物品的重量
int *value = new int[n];//物品的价值
int *bestPath = new int[n];//最佳路径
int *judge = new int[2]; //判断左右分支
int currentWeight=0;//当前重量
int currentValue=0;//当前价值
void dfs(int i) {
if(i>n){
if (currentValue > maxValue) {
maxValue = currentValue;
for(i=1;i<=n;i++){
bestPath[i] = judge[i];
}
}
}
else
{
for (int j = 1; j >= 0; j--) {
judge[i] = j;
if (currentWeight + weight[i]* judge[i] <= BackpackVolume) {
currentWeight += weight[i] * judge[i];
currentValue += value[i] * judge[i];
dfs(i + 1);
currentWeight-= weight[i] * judge[i];
currentValue -= value[i]* judge[i];
}
}
}
}
int main()
{
int i;
maxValue = 0;
cout << "请输入背包最大容量:" << endl;;
cin >> BackpackVolume;
cout << "请输入物品个数:" << endl;
cin >> n;
cout << "请依次输入物品的重量:" << endl;
for (i = 1; i <= n; i++)
cin >> weight[i];
cout << "请依次输入物品的价值:" << endl;
for (i = 1; i <= n; i++)
cin >> value[i];
dfs(1);
cout << "最大价值为:" << endl;
cout << maxValue << endl;
cout << "被选中的物品的标号依次是:" << endl;
for (i = 1; i <= n; i++){
if (bestPath[i] == 1)
cout << i << " ";
}
cout << endl;
return 0;
}
|