01背包问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
给定n种物品和一背包。物品i的重量是wi>0,其价值为vi>0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? (要求使用回溯法)
输入格式
第一行输入物品数量和背包容量 第二行输入所有物品重量 第三行输入所有物品价值
输出格式
第一行输出最大价值 第二输出放置方案
样例
4 6
5 3 2 1
4 4 3 1
8
0 1 1 1