蛮力法解01背包问题

Jocelynn / 2023-05-03 / 原文

#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