C++_背包问题求解

问题描述

问题描述：假设有n个物品，其体积分别表示为w1、w2……wn，并且有一个最大可装载体积为T的背包。任务是从这n个物品中选择若干个，使得它们的总体积恰好等于背包的容量。如果可以实现，则说明该背包问题存在解；反之则无解；

求解方法：首先将这些物品按照一定顺序排列，然后逐个尝试将其放入背包中。每次装入一个物品后，检查当前背包内已装入物品的总体积是否超过了T。若未超过，则继续装入下一个；若超过，则放弃该物品并尝试下一个。当无法再装入其他物品时，若此时背包尚未被填满，则说明当前选择不合适，需从背包中移除最后装入的物品，并重新在剩余未选中的物品中寻找合适的组合。重复上述过程直到找到满足条件的组合（有解）或所有可能的选择都被穷尽（无解）；

输入输出样例：当T=10且W=（4，7，3，5，4，2）时运行程序后，输出结果为Wi=（4，4，2）。

设计思路

设计思路：设置一个一维数组W[1:n]用于存储n个物品的体积信息，并使用栈S[1:n]来记录已经被选中的物品编号。其中T表示背包的最大承载能力，i代表当前待处理的物品编号。每当有一个新的物品被加入栈中时，在T中减去该物体对应的体积值。如果此时T-W[i]≥0，则表示该物体可以被选中；若T-W[i]<0，则表明该物体不能被选中。当i>n时意味着所有可能的选择都已被尝试过，在这种情况下需要从栈