蛮力法之背包问题

问题:

? ? ? ? ? ? ?有 n 个重量分别是 w1,w2....,wn 的物品（物品编号为 1-n）它们的价值分别为 v1,v2,...,vn

给定一个容量为 W 的背包。设计从这些物品中选取一部分放入该背包的方案。

每个物品要么选中要么不选中【其实每个物品只有 1 件】，要求选中的物品不仅能够放在背包中，而且具有最大的价值。

并对如下所展示的 5 个物品求出 W=10 时的最佳解。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?物品编号? ? ? ? ? ? ?重量? ? ? ? ? ? 价值

? ? ? ? ? ? ? ? ? ?

思路:

????????

1. 预先定义了物品的重量数组w和价值数组v，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

2. 定义了一个长度为5的数组x，用于记录物品的选取状态。x[i]的取值为1表示选取第i个物品，取值为0表示不选取第i个物品。

3. 定义了变量maxv，用于记录最大的总价值。

4. 定义了数组ans，用于记录最优解的选取状态。

5. 定义了深度优先搜索函数dfs，其中参数i表示当前正在考虑的物品的索引，ww表示当前已选取的物品的总重量，vv表示当前已选取的物品的总价值。

6. 在dfs函数中，当遍历完所有物品时（i == 5），检查当前选取状态的总重量是否不超过10，并且当前总价值是否大于最大价值。如果满足条件，更新最大价值maxv，并将当前选取状态记录到数组ans中。

7. 在dfs函数中，首先假设选取当前物品（x[i] = 1），然后递归调用dfs函数选择下一个物品（i + 1），并更新总重量ww和总价值vv。

8. 然后，在dfs函数中，不选取当前物品（x[i] = 0），然后递归调用dfs函数选择下一个物品（i + 1），并保持总重量ww和总价值vv不变。

9. 在主函数中，调用dfs函数从第一个物品开始进行深度优先搜索。

10. 最后，输出最优解的选取状态ans和最大价值maxv。

代码:

#include<iostream>
using namespace std;
int w[5] = { 2,2,6,5,4 }, v[5] = { 6,3,5,4,6 }; // 物品的重量和价值
int x[5]; // 记录物品的选取状态
int maxv = 0; // 最大价值
int ans[5]; // 最优解

// 深度优先搜索函数
void dfs(int i, int ww, int vv)
{
    if (i == 5) { // 当遍历完所有物品时
        if (ww <= 10 && vv > maxv) { // 如果总重量不超过10，并且当前价值大于最大价值
            maxv = vv; // 更新最大价值
            for(int i=0;i<5;i++) // 将当前选取状态记录到最优解中
                ans[i]=x[i];
        }
        return; // 返回上一层递归
    }

    x[i] = 1; // 选取当前物品
    dfs(i + 1, ww + w[i], vv + v[i]); // 递归选择下一个物品
    x[i] = 0; // 不选取当前物品
    dfs(i + 1, ww, vv); // 递归选择下一个物品
}

int main()
{
    dfs(0, 0, 0); // 从第一个物品开始进行深度优先搜索
    for(auto x:ans)
        cout<<x; // 输出最优解的选取状态
    cout<<endl;
    cout << maxv; // 输出最大价值
    return 0;
}