# 这个前端竟然用动态规划写瀑布流布局？给我打死他！

## 准备工作

```let SISTERS = [
'https://pic3.zhimg.com/v2-89735fee10045d51693f1f74369aaa46_r.jpg',
'https://pic1.zhimg.com/v2-ca51a8ce18f507b2502c4d495a217fa0_r.jpg',
'https://pic1.zhimg.com/v2-c90799771ed8469608f326698113e34c_r.jpg',
'https://pic1.zhimg.com/v2-8d3dd83f3a419964687a028de653f8d8_r.jpg',
... more 50 items
]
```

```let loadImgHeights = (imgs) => {
return new Promise((resolve, reject) => {
const length = imgs.length
const heights = []
let count = 0
const load = (index) => {
let img = new Image()
const checkIfFinished = () => {
count++
if (count === length) {
resolve(heights)
}
}
const ratio = img.height / img.width
const halfHeight = ratio * halfInnerWidth
// 高度按屏幕一半的比例来计算
heights[index] = halfHeight
checkIfFinished()
}
img.onerror = () => {
heights[index] = 0
checkIfFinished()
}
img.src = imgs[index]
}
})
}

## 贪心算法

```let greedy = (heights) => {
let mid = Math.round(sum(heights) / 2)
let total = 0
let leftHeights = []
let rightHeights = []
let left = []
let right = []

heights.forEach((height, index) => {
if (sum(leftHeights) > sum(rightHeights)) {
right.push(index)
rightHeights.push(height)
} else {
left.push(index)
leftHeights.push(height)
}
total += height
})

return { left, right }
}

```<div class="wrap" v-if="imgsLoaded">
<div class="half">
<img
class="img"
v-for="leftIndex in leftImgIndexes"
:src="imgs[leftIndex]"
:style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }"
/>
</div>
<div class="half">
<img
class="img"
v-for="rightIndex in rightImgIndexes"
:src="imgs[rightIndex]"
:style="{ width: '100%', height: imgHeights[rightIndex] + 'px' }"
/>
</div>
</div>

## 动态规划

### 小问题拆解

1. 首先去尝试凑高度 `1`：我们知道图片 1 的高度正好是 1，所以此时`dp[0][0]`所填写的值是 `{ max: 1, indexes: [0] }`，也就代表用总高度还剩 1，并且只考虑图片 1 的情况下，我们的最优解是选用第一张图片。
2. 凑高度`2 ~ 7`：由于当前只有 1 可以选择，所以最优解只能是选择第一张图片，它们都是 `{ max: 1, indexes: [0] }`
```高度       1  2  3  4  5  6  7

```

```let mid = Math.round(sum(heights) / 2)
let dp = []
// 基础状态 只考虑第一个图片的情况
dp[0] = []
for (let cap = 0; cap <= mid; cap++) {
dp[0][cap] =
heights[0] > cap
? { max: 0, indexes: [] }
: { max: heights[0], indexes: [0] }
}
```

```高度       1  2  3  4  5  6  7

```

1. 选择当前图片，那么假设当前要凑的总高度为 3，当前图片的高度为 2，剩余的高度就为 1，此时我们可以用剩余的高度去「上一个纵坐标」里寻找「只考虑前面几种图片」的情况下，高度为 1 时的最优解。并且记录 `当前图片的高度 + 前几种图片凑剩余高度的最优解``max1`
2. 不选择当前图片，那么就直接去「只考虑前面几种图片」的上一个纵坐标里，找到当前高度下的最优解即可，记为 `max2`
3. 比较 `max1``max2`，找出更大的那个值，记录为当前状态下的最优解。

1. 凑高度 1：由于图片 2 的高度为 2，相当于是容量超了，所以这种情况下不选择图片 2，而是直接选择图片 1，所以 `dp[1][0]` 可以直接沿用 `dp[0][0]`的最优解，也就是 `{ max: 1, indexes: [0] }`
2. 凑高度 2：
1. 选择图片 2，图片 2 的高度为 4，能够凑成的高度为 4，已经超出了当前要凑的高度 2，所以不能选则图片 2。
2. 不选择图片 2，在只考虑图片 1 时的最优解数组 `dp[0]` 中找到高度为 2 时的最优解： `dp[0][2]`，直接沿用下来，也就是 `{ max: 1, indexes: [0] }`
3. 这种情况下只能不选择图片 2，而沿用只选择图片 1 时的解， `{ max: 1, indexes: [0] }`
3. 省略凑高度 `3 ~ 4` 的情况，因为得出的结果和凑高度 2 是一样的。
4. 凑高度 5：高度为 5 的情况下就比较有意思了：
1. 选择图片 2，图片 2 的高度为 4，能够凑成的高度为 4，此时剩余高度是 1，再去只考虑图片 1 的最优解数组 `dp[0]`中找高度为 1 时的最优解`dp[0][1]`，发现结果是 `{ max: 1, indexes: [0] }`，这两个高度值 4 和 1 相加后没有超出高度的限制，所以得出最优解：`{ max: 5, indexes: [0, 1] }`
2. 不选择图片 2，在图片 1 的最优解数组中找到高度为 5 时的最优解： `dp[0][5]`，直接沿用下来，也就是 `{ max: 1, indexes: [0] }`
3. 很明显选择图片 2 的情况下，能凑成的高度更大，所以 `dp[1][2]` 的最优解选择 `{ max: 5, indexes: [0, 1] }`

```// 尽可能选出图片中高度最接近图片总高度一半的元素
let dpHalf = (heights) => {
let mid = Math.round(sum(heights) / 2)
let dp = []

// 基础状态 只考虑第一个图片的情况
dp[0] = []
for (let cap = 0; cap <= mid; cap++) {
dp[0][cap] =
heights[0] > cap
? { max: 0, indexes: [] }
: { max: heights[0], indexes: [0] }
}

for (
let useHeightIndex = 1;
useHeightIndex < heights.length;
useHeightIndex++
) {
if (!dp[useHeightIndex]) {
dp[useHeightIndex] = []
}
for (let cap = 0; cap <= mid; cap++) {
let usePrevHeightDp = dp[useHeightIndex - 1][cap]
let usePrevHeightMax = usePrevHeightDp.max
let currentHeight = heights[useHeightIndex]
// 这里有个小坑 剩余高度一定要转化为整数 否则去dp数组里取到的就是undefined了
let useThisHeightRestCap = Math.round(cap - heights[useHeightIndex])
let useThisHeightPrevDp = dp[useHeightIndex - 1][useThisHeightRestCap]
let useThisHeightMax = useThisHeightPrevDp
? currentHeight + useThisHeightPrevDp.max
: 0

// 是否把当前图片纳入选择 如果取当前的图片大于不取当前图片的高度
if (useThisHeightMax > usePrevHeightMax) {
dp[useHeightIndex][cap] = {
max: useThisHeightMax,
indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex),
}
} else {
dp[useHeightIndex][cap] = {
max: usePrevHeightMax,
indexes: usePrevHeightDp.indexes,
}
}
}
}

return dp[heights.length - 1][mid]
}

```this.leftImgIndexes = dpHalf(imgHeights).indexes
this.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes)
```

## 总结

0 条评论

• ### 前端动画必知必会：React 和 Vue 都在用的 FLIP 思想实现小姐姐流畅移动。

乍一看，让我们手写出这个逻辑应该是非常复杂的，先看看本文最后要实现的效果吧，和这个案例是非常类似的。

• ### Vue3 跟着尤雨溪学 TypeScript 之 Ref 类型从零实现

Vue3 中，ref 是一个新出现的 api，不太了解这个 api 的小伙伴可以先看 官方api文档。

• ### Vue3中不止composition-api，其他的提案(RFC)也很精彩。

最近一段时间，Vue3带来的新能力composition-api带来了比较大的轰动，虽然是灵感是源React Hook，但是在很多方面却超越了它。但是除了com...

• ### 程序员修神之路--设计一套RPC框架并非易事

可以这么说，http协议是基于TCP协议的，底层的数据传输可以说是利用的socket

• ### 编程小白 | 每日一练（187）

这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数，我们大多数人想要从编程小白进阶到高手，需要经历的是日积月累的学习，那么如何学习呢？当然是每天都...

• ### 34.opengl PBR-理论

phong光照模型，没有遵循能量守恒，对光照的反应看起来并不真实，PBR是对phong光照模型的一次革命性升级，但是最基本的概念并没有变，都是要计算 反射、漫反...

• ### 为什么说全栈工程师是未来？| 长文多图

谨以此文献给每一个为成为优秀全栈工程师奋斗的人。 节选自《Growth: 全栈工程师学习手册》 ? 技术在过去的几十年里进步很快，也将在未来的几十年里发展得更快...

https://www.cnblogs.com/poloyy/category/1690628.html

• ### Python|图形排版

小明需要在一篇文档中加入 N 张图片，其中第 i 张图片的宽度是 Wi，高度是 Hi。

• ### [开源]DSLogic开源逻辑分析仪方案分享

今天来分享一个开源项目——DSLogic，它是一款基于FPGA的逻辑分析仪，是由国内的梦源实验室（DreamSourceLab）做出的开源软硬件产品，从FPGA...