神马作文网求助一道c++背包问题 需要用递归的方法解决
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/19 04:50:02
求助一道c++背包问题 需要用递归的方法解决
已知背包可放入的质量为S,现有n件物品,质量分别为w1,w2,w3...wn,能否从这n件物品中选择若干件放入此背包,使之重量恰好为S,若存在一种符合要求的选择,则称背包问题有解,否则背包问题无解.
已知背包可放入的质量为S,现有n件物品,质量分别为w1,w2,w3...wn,能否从这n件物品中选择若干件放入此背包,使之重量恰好为S,若存在一种符合要求的选择,则称背包问题有解,否则背包问题无解.
1.排序,删掉大于S的物品.
2.编码,放入为1,不放入为0.一个编码100111…就是一种物品的选择.
3.从00000开始到11111,遍历一遍就OK了.
想用递归的话
1.排序,从小到大
2.从0000开始,如果总质量小于S,2进制序列加1,作为变量传送到下一层递归函数中
3.如果大于S,返回0
4.如果等于S,返回1以及当前的2进制序列
2.编码,放入为1,不放入为0.一个编码100111…就是一种物品的选择.
3.从00000开始到11111,遍历一遍就OK了.
想用递归的话
1.排序,从小到大
2.从0000开始,如果总质量小于S,2进制序列加1,作为变量传送到下一层递归函数中
3.如果大于S,返回0
4.如果等于S,返回1以及当前的2进制序列