0. 前言
经典的动态规划题目:背包问题
1. 问题描述
01背包(ZeroOnePack): 有N件物品和一个承重为bear的背包。每种物品均只有一件。第i件物品的重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使价值总和最大。
完全背包(CompletePack): 有N种物品和一个承重为bear的背包,每种物品都有无限件可用。第i种物品的重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包承重,且价值总和最大。
多重背包(MultiplePack): 有N种物品和一个承重为bear的背包。第i种物品最多有amount[i]件可用,每件重量是weight[i],价值是value[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重,且价值总和最大。
more >>