问题可以描述为:给定一组共 n 个物品,每种物品都有自己的重量 wi, i=1~n 和价值 vi, i=1~n,在限定的总重量(背包的容量 C)内,如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中,最优子集对应 n 元解向量(x1,…xn), 为方便调试,采用文件输入,标准输出(或文件输出也可)的形式。数据输入的格式如下:每组测试数据 包含 n+1 行,第 1 行为 C 和 n,表示背包容量为 C 且有 n 个物品,接下来 n 行为这 n 个物品的
打开文件 源码可取 可以运行 无需修改
今天给大家分享0-1背包问题的基本解题思路。小白教程,不涉及到动态规划以及状态转移方程等术语,随着后面的更新,这些都会讲到。
问题描述
给你一个可容纳最大重量为 w 的背包和 N 个物品,每个物品有重量和价值两个属性。其中第 i 个物品的重量为 weight[ i ],价值为value[ i ]。现在要你用这个背包装物品,每个物品只能装一次。请问你能装的最大价值是多少?
举例
· 商品数:5 背包容量:20
·