02_05_算法_0-1背包问题的几何作图解读

本文主要是介绍02_05_算法_0-1背包问题的几何作图解读，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先，把0-1背包问题描述一遍：

　　给你一个可装载最大重量为maxWeight的背包和N个物品，每个物品有重量(w)和价值(v)两个属性。

　　其中第i个物品的重量为w[i]，价值为v[i]，现在问，这个背包能装的最大价值是多少？

一，为了分析0-1背包问题，我们用如下的特殊值的（重量数组、价值数组）作为特例：

//重量数组
int[] ws = new int[]{1,2,3,4,5,6};

//价值数组
int[] vs = new int[]{1,2,3,4,5,6};

二，分析方法：设X轴为 “放入重量为 x 的物品”，设Y轴为 “限定总重量为 y ”，那么通过不断地填充极值，最终会形成一个，形如如下图的极值柱状图：

三，具体的极值填充过程如下（略，等待后续继续写，暂时没有时间）

这样，0-1背包问题，就是基于一个二维数组，或者说二维坐标系的，极值填充选择问题。

同理，对于更复杂的类似问题，可以理解为更多维的数组填充问题。

本文是为了用图形化的方式，方便理解。

具体的代码，可以参照labuladong的0-1背包问题的代码。

这篇关于02_05_算法_0-1背包问题的几何作图解读的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程