蛮力法之背包问题

2023-12-22 06:30:47

问题:

? ? ? ? ? ? ?有 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;
}

文章来源:https://blog.csdn.net/a17783481239/article/details/135142225
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。