c++回顾|【c++回顾】3.1经典算法问题-0/1背包价值最大问题背包问题|算法|vector|迭代遍历

问题描述：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？每种物品只有一个
解题思路：有了遍历n维0/1数组的方法，我们可以直接遍历所有的结果，记录价值最大时的拿取方案，详见我的上一篇文章。
直接上代码：

//给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ //有了遍历n维0/1数组的方法，我们可以直接遍历所有的结果，记录价值最大时的拿取方案#include "pch.h" #include #include using namespace std; //给出拿取情况向量与重量列表向量，求解当前背包重量 int CalculateWeight(vector taken_items, vector weights) { int weight = 0; for (int i = 0; i < taken_items.size(); i++) weight = weight + taken_items[i] * weights[i]; return weight; } //递归实现n维0/1数组的取值情况遍历 //使用时vec初始化为全零数组，i初始化为0,递归前先进行一次operation //递归时vec的第i个元素进行变化 void BackpackProblem(vector taken_items, int i, int capacity, vector weights, vector values, vector &solution, int* solution_value) { //如果i超出taken_items范围，则返回 if (i == taken_items.size()) return; //如果超出背包重量，则返回 if (CalculateWeight(taken_items, weights) > capacity) return; //递归 BackpackProblem(taken_items, i + 1, capacity, weights, values, solution, solution_value); //变化第i个元素，进行操作 taken_items[i] = 1; //operation //计算当前价值并与最佳价值比较,如果当前方案更优就取当前方案，更新两个量 int current_value = https://www.it610.com/article/CalculateWeight(taken_items, values); if (current_value> *solution_value) { solution = taken_items; *solution_value = https://www.it610.com/article/current_value; } //递归 BackpackProblem(taken_items, i + 1, capacity, weights, values, solution, solution_value); } //根据拿取情况向量输出结果 void PrintResult(vector taken_items, int best_value) { cout << "【最优解】拿取第"; for (int i = 0; i < taken_items.size(); i++) if (taken_items[i])cout << i << ' '; cout <<"个物品"<< endl; cout << "【最优解】最大价值为：" << best_value << endl; }int main() { //初始化 int capacity; vector weights; vector values; int number; cout << "输入背包容量及物品件数：" << endl; cin >> capacity >> number; cout << "输入这" << number << "个物品的重量" << endl; for (int i = 0; i < number; i++) { int weight; cin >> weight; weights.push_back(weight); } cout << "输入这" << number << "个物品的价值" << endl; for (int i = 0; i < number; i++) { int value; cin >> value; values.push_back(value); } //定义拿取情况向量 vector taken_items(number, 0); //定义最佳拿取情况向量 vector solution(number, 0); //定义最大价值 int solution_value = https://www.it610.com/article/0; //定义迭代元素i int i = 0; //由于一个都不拿肯定不是最优解，故无需操作当前向量，直接开始递归 BackpackProblem(taken_items, i, capacity, weights, values, solution, &solution_value); //输出最优结果 PrintResult(solution, solution_value); return 0; } /* 输入 10 6 1 8 4 3 5 2 1 2 3 4 5 6 */