C++背包最大容量问题

问题描述、

问题描述：给定n种物品和一个背包，在第i种物品的重量为wi、价值为vi的情况下，请问：在给定n种物品和一个背包的情况下，应如何选择装入背包的物品以使装入背包中的物品总价值达到最大？

问题分析：首先将n个物体按一定顺序排列，并逐个放入背包。每次放置一个后立即检查当前背包装载物总体积是否超出容量限制C。如果放置该物块后不超出容量限制，则将其放入；否则将其舍弃并考虑下一个物体。当放入某物体后仍无法满足条件时（即剩余空间不足以再容纳其他物体），则记录此时背包装载物总价值为V；如果当前背包装载物总价值V达到最大可能值，则记下这一组被选中的物体组合，并移除最后一个被放置进去的物体；接着处理尚未被放入的其他物体直至全部处理完毕之后输出使总价值V最大的这组被选中的物体组合

输入样例： 物品体积分别为{4，7，3，5，4，2}；价值分别为{4，7，3，5，4，1}

总收益的最大值是10，在其组合中包括体积和价值均为7的第二件物品以及体积和价值均为3的第一件物品。

设计思路

设计思路：初始化一维数组w用于存储n个物品的体积信息，并创建辅助数组vi（价值）、v（最优索引）、s（选中索引）。设定背包容量C和目标价值V，并记录当前最优总价值Vmax及对应组合v[1:n]。对于每一个待选物品i（从1到n），执行以下操作：扣除该物品体积W[i]于剩余容量C中（即C = C - W[i]）