#include <iostream> using namespace std; struct thing { int weight;//物品重量 int value;//物品价值 int number;//物品序号 }; thing things[10];//假设最多有10个物品 int thingsCount;//物品数量 int bagSize;//背包容量 int maxTotalValue;//最大总重量 int currentWeight;//当前重量 int currentValue;//当前价值 int currentPath[10];//存储当前路径 int bestPath[10];//存储最优路径 int bruteForce(int number) {//蛮力法,参数为物品序号 if (number == thingsCount) {//最内层函数的返回条件:当已经遍历到最后一个物品时 if (currentValue > maxTotalValue && currentWeight <= bagSize) {//若当前重量更大,只有当前容量小于背包容量才可以更新 maxTotalValue = currentValue; for (int i = 0; i < number; i++) { bestPath[i] = currentPath[i];//将当前路径用最优路径数组保存 } } return maxTotalValue;//递归到叶结点,返回遍历该路径后的当前最大总重量 } //序号为number+1的物品装入背包的情况 currentWeight += things[number].weight; currentValue += things[number].value; currentPath[number] = 1; bruteForce(number + 1);//向下递归 //序号为number+1的物品不装入背包的情况 currentWeight -= things[number].weight; currentValue -= things[number].value; currentPath[number] = 0; bruteForce(number + 1);//向下递归 //当装入和不装入该物品的情况都遍历完后,返回当前得到的最大总重量 return maxTotalValue; } int main() { //初始化物品数、背包容量和物品数组 cout << "请输入物品数:"; cin >> thingsCount; cout << "请输入背包容量:"; cin >> bagSize; for (int i = 0; i < thingsCount; i++) { cout << "请输入序号为" << i + 1 << "的物品的重量和价值: "; cin >> things[i].weight >> things[i].value; } //蛮力法计算最优组合 maxTotalValue = bruteForce(0);//0作为参数传入,对应递归的起点 cout << endl; cout << "========蛮力法得最优解如下========"<<endl; cout << "背包可以装入的最大容量为:" << maxTotalValue << endl; //输出最优路径(最大容量选取的物品序号) cout << "选取了序号为:"; for (int i = 0; i < thingsCount; i++) { if (bestPath[i]) cout << i + 1 << " "; } cout << "的物品装入背包" << endl; system("pause"); return 0; } //请输入物品数:4 //请输入背包容量:10 //请输入序号为1的物品的重量和价值 : 7 42 //请输入序号为2的物品的重量和价值 : 3 12 //请输入序号为3的物品的重量和价值 : 4 40 //请输入序号为4的物品的重量和价值 : 5 25
标签:10,01,cout,int,蛮力,物品,法解,thingsCount From: https://www.cnblogs.com/Jocelynn/p/17367077.html