稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

彻底搞懂背包问题

背包问题Knapsack Problem)是指给定一个容量固定为W的背包和一组数量为n的物品,每个物品的重量为wi,价值为vi,要求从物品中选择若干放入背包,使总物品重量不超过背包容量,并且使价值最大。这是动态规划的一类非常典型的问题。

背包问题如果每种物品数量只有一个,那么每个物品只有两种状态『放入背包』和『不放入背包』,这个一般称作0-1背包问题;如果每种物品的数量无限又称完全背包。

典型题目

题目 题解 说明
题解
题解
题解
题解
题解
题解

参考资料

Comments