0/1背包求解器
工具介绍及使用方法
背包问题求解器,一次求出「在容量内怎么装最值钱」。输入区每行一个物品,格式为「重量,价值」,
例如:
使用方法:
1. 选择背包类型:
· 0/1 背包:每件物品最多选 1 次;
· 完全背包:每件物品可选任意多次;
2. 填写背包容量(正整数;填小数会四舍五入并提示);
3. 点击「开始计算」,结果表格给出每件物品的选中次数与一行汇总,文本框再给一份文字汇总;
4. 结果支持一键复制与导出 CSV。
算法上使用经典一维动态规划:0/1 背包逆序滚动、完全背包正序滚动,并记录回溯信息以还原具体的选中方案,因此给出的组合确实能达到最优总价值,而不是只有一个数字。容量上限 100000、物品数上限 500,超出会按上限收敛并提示,不会把浏览器卡死。
例如:
3,54,62,35,9使用方法:
1. 选择背包类型:
· 0/1 背包:每件物品最多选 1 次;
· 完全背包:每件物品可选任意多次;
2. 填写背包容量(正整数;填小数会四舍五入并提示);
3. 点击「开始计算」,结果表格给出每件物品的选中次数与一行汇总,文本框再给一份文字汇总;
4. 结果支持一键复制与导出 CSV。
算法上使用经典一维动态规划:0/1 背包逆序滚动、完全背包正序滚动,并记录回溯信息以还原具体的选中方案,因此给出的组合确实能达到最优总价值,而不是只有一个数字。容量上限 100000、物品数上限 500,超出会按上限收敛并提示,不会把浏览器卡死。
留言板
全部留言 →-
还没人说话,来占个沙发?