信息学一本通2134: 信息学奥赛一本通T1270-混合背包题解（求解将哪些物品装入背包可使这些物品）

旧巴黎算法基础篇 2023-11-09 02:53:02 34 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn，有的物品只可以取一次，有的物品可以取无限次，有的物品可以取的次数有一个上限，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。