问题:
有 n 个重量分别是 w1,w2....,wn 的物品（物品编号为 1-n）它们的价值分别为 v1,v2,...,vn
给定一个容量为 W 的背包。设计从这些物品中选取一部分放入该背包的方案。
每个物品要么选中要么不选中【其实每个物品只有 1 件】，要求选中的物品不仅能够放在背包中，而且具有最大的价值。
并对如下所展示的 5 个物品求出 W=10 时的最佳解。
物品编号 重量 价值
思路:
-
预先定义了物品的重量数组w和价值数组v，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。
-
定义了一个长度为5的数组x，用于记录物品的选取状态。x[i]的取值为1表示选取第i个物品，取值为0表示不选取第i个物品。
-
定义了变量maxv，用于记录最大的总价值。
-
定义了数组ans，用于记录最优解的选取状态。
-
定义了深度优先搜索函数dfs，其中参数i表示当前正在考虑的物品的索引，ww表示当前已选取的物品的总重量，vv表示当前已选取的物品的总价值。
-
在dfs函数中，当遍历完所有物品时（i == 5），检查当前选取状态的总重量是否不超过10，并且当前总价值是否大于最大价值。如果满足条件，更新最大价值maxv，并将当前选取状态记录到数组ans中。
-
在dfs函数中，首先假设选取当前物品（x[i] = 1），然后递归调用dfs函数选择下一个物品（i + 1），并更新总重量ww和总价值vv。
-
然后，在dfs函数中，不选取当前物品（x[i] = 0），然后递归调用dfs函数选择下一个物品（i + 1），并保持总重量ww和总价值vv不变。
-
在主函数中，调用dfs函数从第一个物品开始进行深度优先搜索。
-
最后，输出最优解的选取状态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;
}
