<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="referrer" content="never" />
<title>Document</title>
<style>
* {
margin: 0;
box-sizing: border-box;
padding: 0;
}
body {
max-width: 500px;
margin: auto;
}
.link {
display: block;
padding: 8px;
text-align: center;
color: red;
}
.wrap {
display: flex;
}
.half {
width: 50%;
padding: 8px;
}
.img {
border-radius: 8px;
}
</style>
</head>
<body>
<a class="link" href="./greedy.html">查看贪心算法结果</a>
<div id="app">
<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>
</div>
<script src="https://sl1673495.github.io/dp-waterfall/vue.js"></script>
<script src="https://sl1673495.github.io/dp-waterfall/mock.js"></script>
<script src="https://sl1673495.github.io/dp-waterfall/util.js"></script>
<script>
new Vue({
el: '#app',
async created() {
const imgHeights = await loadImgHeights(this.imgs)
this.imgHeights = imgHeights
this.leftImgIndexes = dpHalf(imgHeights).indexes
this.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes)
this.imgsLoaded = true
},
data() {
return {
imgs: SISTERS.slice(0, 10),
imgHeights: [],
imgsLoaded: false,
leftImgIndexes: [],
rightImgIndexes: []
}
}
}) // 尽可能选出图片中高度最接近图片总高度一半的元素
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]
}
</script>
</body>
</html>
<!-- 模拟数据 -->
<!-- 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',
'https://pic1.zhimg.com/v2-09eefac19ac282684f60a202aa9abb2c_r.jpg',
'https://pic3.zhimg.com/v2-a7340ebca1f7a4f65190583b4ab3a482_r.jpg',
'https://pic2.zhimg.com/v2-37860484a1a73257178e95267c7db641_r.jpg',
'https://pic2.zhimg.com/v2-7fc30291c807d07d2d26c5a8ffdd3b89_r.jpg',
'https://pic4.zhimg.com/v2-02efe89495be4f68f6b7b6c510da36cf_r.jpg',
'https://pic3.zhimg.com/v2-1e375cbcad7ae119c34a1357c9e8f182_r.jpg',
'https://pic4.zhimg.com/v2-aeadbc3d02af2631e3a7acd0dc72b01b_r.jpg',
'https://pic3.zhimg.com/v2-a47effc7163387c1ad7ccfc90ec3e91e_r.jpg',
'https://pic3.zhimg.com/v2-a71fad6a1fee2614ad95a4bae0376eb6_r.jpg',
'https://pic3.zhimg.com/v2-861f71f28e361237003aa1c88188f326_r.jpg',
'https://pic4.zhimg.com/v2-525c8002eb619387e7a31f67169f8a2b_r.jpg',
'https://pic4.zhimg.com/v2-0dcbcf5a48a97afab7439e09af65c98f_r.jpg',
'https://pic1.zhimg.com/v2-d640737ff5eac65fe30375f324512d00_r.jpg',
'https://pic1.zhimg.com/v2-6e92b4576b93302ad5fe04c7e95e375c_r.jpg',
'https://pic1.zhimg.com/v2-5e4a1221996179cbacc5d7450d25f908_r.jpg',
'https://pic3.zhimg.com/v2-7f58a7d6e8b1ed3f653a96ae9d6e1e2e_r.jpg',
'https://pic4.zhimg.com/v2-fb767fd3f56591a3c4b2b4089c47776f_r.jpg',
'https://pic2.zhimg.com/v2-6b9847e11d3a8cac8ac0ef52bffd9af5_r.jpg',
'https://pic2.zhimg.com/v2-6f2119f99200fc61abc246eea36f25b1_r.jpg',
'https://pic4.zhimg.com/v2-2103acaf025ceda331a0dd59022443ab_r.jpg',
'https://pic2.zhimg.com/v2-edc1b118c420939c545b1449344139b5_r.jpg',
'https://pic2.zhimg.com/v2-d94530f491f23c61659ef458ac8a9db5_r.jpg',
'https://pic2.zhimg.com/v2-ff15820a9c1cb8e2bb0af1048ea81145_r.jpg',
'https://pic4.zhimg.com/v2-a8fb0a1d8581e4bfce905791271711c7_r.jpg',
'https://pic2.zhimg.com/v2-1008cd2c72129809cc348cdc04310475_r.jpg',
'https://pic1.zhimg.com/v2-88f4b396d246250f93407cdba3b61e10_r.jpg',
'https://pic2.zhimg.com/v2-6b5c409d6957c0355db0152c54ff4b75_r.jpg',
'https://pic4.zhimg.com/v2-c49423b4c6903c4176e897fbcf46691f_r.jpg',
'https://pic2.zhimg.com/v2-1eee6f2ab9545b615ed556cbd31dea71_r.jpg',
'https://pic4.zhimg.com/v2-7807a06576ee62e0f29a58d29441dc5f_r.jpg',
'https://pic4.zhimg.com/v2-579e97a1506a5cd380dbef02e263c3a7_r.jpg',
'https://pic2.zhimg.com/v2-0c813318a3c91b18a654c0c125c3271d_r.jpg',
'https://pic1.zhimg.com/v2-fb74dd10dfa060d819a3bfcafc138c78_r.jpg',
'https://pic3.zhimg.com/v2-5472d0672795ee8135385554c90ab966_r.jpg',
'https://pic1.zhimg.com/v2-89cc5bd399f5a42e2900acdb9b127014_r.jpg',
'https://pic3.zhimg.com/v2-d7158a82c2b2ed2fc7a415bda48dab96_r.jpg',
'https://pic2.zhimg.com/v2-758baa29da4d447eccddb0080e4050b9_r.jpg',
'https://pic2.zhimg.com/v2-f9a72b638c60c8fa68ef93cb217483f1_r.jpg',
'https://pic2.zhimg.com/v2-edcc5bbc6691411b17b422b3e25f14ad_r.jpg',
'https://pic1.zhimg.com/v2-a7ef8b82cb11291666ba606015d6eed4_r.jpg',
'https://pic1.zhimg.com/v2-423468f5a654f5b67dafdf5d5d75a10c_r.jpg',
'https://pic3.zhimg.com/v2-a9755f6951c922127fba3bbfebc78422_r.jpg',
'https://pic3.zhimg.com/v2-3dc6ef1efd2df5eab50c0d67ed47483a_r.jpg',
'https://pic3.zhimg.com/v2-f08f150f0242d484ffdb73069c446f3e_r.jpg',
'https://pic1.zhimg.com/v2-81f18f1030e7b5b144b793ff2bc2cbf4_r.jpg',
'https://pic3.zhimg.com/v2-b243a0eeb9042f85ecc742cfbd3b9bd6_r.jpg',
'https://pic4.zhimg.com/v2-d4006e56e24617b3d990112b72eb4ef7_r.jpg',
'https://pic4.zhimg.com/v2-f7c9fab09f236a8e2b28b18f6ba3595b_r.jpg',
'https://pic2.zhimg.com/v2-0f3dc849ac1b34a8069aa1aa0a539971_r.jpg',
'https://pic3.zhimg.com/v2-43dfe58de82d36af7260c3463bd9bede_r.jpg',
'https://pic1.zhimg.com/v2-11e3e7ea0c4ce093e877bf1d988cd894_r.jpg',
'https://pic3.zhimg.com/v2-d0d16e5b4a69130144875f2d79d01b32_r.jpg',
'https://pic2.zhimg.com/v2-d6ff4148843f5a760190366d28d6cfe9_r.jpg',
'https://pic4.zhimg.com/v2-62f67089abb47f37b58315391f752b03_r.jpg',
'https://pic1.zhimg.com/v2-4992fa5c6ccfe07a7e25aacd7d4389a8_r.jpg',
'https://pic3.zhimg.com/v2-9f71ad346e88af28e6b8cb8ee0a8ac32_r.jpg',
'https://pic4.zhimg.com/v2-31a429a944bc815522231b95676cf72b_r.jpg',
'https://pic1.zhimg.com/v2-383283ac28da8aa0f7dba4e544f9552c_r.jpg',
'https://pic2.zhimg.com/v2-bd8fbd3c40a41e2c63cd58754c2c489d_r.jpg',
'https://pic4.zhimg.com/v2-12f7d76020eb78b0fe2aebaae65274e7_r.jpg',
'https://pic1.zhimg.com/v2-a50ec3d523be1ecd524d9602abe87e40_r.jpg',
'https://pic3.zhimg.com/v2-469d8f14fc10d2d8182eff0398fb68fa_r.jpg',
'https://pic4.zhimg.com/v2-0dac3cc92a446347cc1670d94e8bd747_r.jpg',
'https://pic3.zhimg.com/v2-f5bf696f8acae86f231f20df3f43bd16_r.jpg',
'https://pic2.zhimg.com/v2-4d74e5de7c5600809ccec2a4b6351ee1_r.jpg',
'https://pic3.zhimg.com/v2-8bba115f2a0343e6606cbcb2d339ea86_r.jpg',
'https://pic1.zhimg.com/v2-b33389ead69a664725e6a6efe9e1a988_r.jpg',
'https://pic3.zhimg.com/v2-57ea9c52c9e00ce762c79fab1da9111e_r.jpg',
'https://pic1.zhimg.com/v2-548f01c4ad671da81b961f700a0c45b8_r.jpg',
'https://pic4.zhimg.com/v2-45143673d7f949a97247119ba3862e0b_r.jpg',
'https://pic4.zhimg.com/v2-d7abf6a721c1183909c8b348cba9debf_r.jpg',
'https://pic1.zhimg.com/v2-a564369b32fe85d6310b58dac6c40fac_r.jpg',
'https://pic3.zhimg.com/v2-153150afd146298623e63b2056877082_r.jpg',
'https://pic2.zhimg.com/v2-5312411bbd58c14debee18150d943b9d_r.jpg',
'https://pic1.zhimg.com/v2-7910bb9e0613bc377dc244f6713ef2e0_r.jpg',
'https://pic2.zhimg.com/v2-2868a6075c4f648c3d97b78b1df68f2d_r.jpg',
'https://pic4.zhimg.com/v2-98a166f0edc3d064f0ef3358ff2a8c87_r.jpg',
'https://pic2.zhimg.com/v2-3b6a5eab816b371332d95623f18947a9_r.jpg',
'https://pic2.zhimg.com/v2-d44e8a53a856c313279760625f69cbdd_r.jpg',
'https://pic1.zhimg.com/v2-945cc1345ba32f52aa67e8a0594d4fc4_r.jpg',
'https://pic4.zhimg.com/v2-7d885ade5003272d526a3aced4d50827_r.jpg',
'https://pic3.zhimg.com/v2-955aaecee40f478cc3c2580c60ef03f2_r.jpg',
'https://pic3.zhimg.com/v2-97a0efb176293cd30e2e9733aac069a6_r.jpg',
'https://pic4.zhimg.com/v2-8d08cc7aee594b37c4828e24ff66e20f_r.jpg',
'https://pic2.zhimg.com/v2-c30352f21f163d53b290c35eee8e3065_r.jpg',
'https://pic1.zhimg.com/v2-2d220acf8a077d18e9c47de00f782cb0_r.jpg',
'https://pic1.zhimg.com/v2-b69038f78b5dfcb6c0256852948ba384_r.jpg',
'https://pic3.zhimg.com/v2-6dc5beaad04afe77f0e87485c9f8762a_r.jpg',
'https://pic3.zhimg.com/v2-5d78d34b368fd3fec158429164c612ca_r.jpg',
'https://pic3.zhimg.com/v2-bdbadea8f53be51e761e31aeeabff4a2_r.jpg',
'https://pic4.zhimg.com/v2-87013628e7f95cf30becbed746a819d3_r.jpg',
'https://pic1.zhimg.com/v2-9e1b3c9bb42646a44de6757efa5a24e8_r.jpg',
'https://pic4.zhimg.com/v2-301b99440342852a345d37b5dd67b4d3_r.jpg',
'https://pic3.zhimg.com/v2-5d63cf93cdca41cb80d3bd2b0ce72dce_r.jpg',
'https://pic4.zhimg.com/v2-4b327471ee616beb7ce2abeaec506fbb_r.jpg',
'https://pic4.zhimg.com/v2-0682cd187f7a15505b3ba2919204c027_r.jpg',
'https://pic3.zhimg.com/v2-3884d65059d51f63be3ca1f8bc27a37e_r.jpg',
'https://pic1.zhimg.com/v2-a0c806558a53d0b1577566850704b04c_r.jpg',
'https://pic2.zhimg.com/v2-b92bf13992d74b7888bd06a2f3f51181_r.jpg',
'https://pic2.zhimg.com/v2-8acdec38dda6eb575777e3f9a247bbd5_r.jpg',
'https://pic3.zhimg.com/v2-570bdbc52dc3e3cbab0cbdc09048163a_r.jpg',
'https://pic4.zhimg.com/v2-3e16f01786e245754e0cfc98ccf0306f_r.jpg',
'https://pic4.zhimg.com/v2-6ca522a890519748c9d20497c56e155b_r.jpg',
'https://pic3.zhimg.com/v2-181ef76d23aca2f7fde19cf5e98e7fee_r.jpg',
'https://pic3.zhimg.com/v2-5fdcb41a0e8c301df5dbc4d5f914cdca_r.jpg',
'https://pic1.zhimg.com/v2-80fba73035db71c7b9fec549db3ac5c4_r.jpg',
'https://pic2.zhimg.com/v2-2cc43b91a34e50bf3205e0d29d31aa0d_r.jpg',
'https://pic1.zhimg.com/v2-f059c192d39c5c9be8b820768366572c_r.jpg',
'https://pic1.zhimg.com/v2-e3e6f90fde10f49e94755ef0476b0e04_r.jpg',
'https://pic4.zhimg.com/v2-975ad0f2e634b070a7daa0342734fccb_r.jpg',
'https://pic1.zhimg.com/v2-6e9959fa8ead0e5f4cc2112621ed6ecc_r.jpg',
'https://pic3.zhimg.com/v2-14e765d63a1abf9e61b642d312ec820a_r.jpg',
'https://pic2.zhimg.com/v2-3abad50daacc4f21ac253d791fac1c9d_r.jpg',
]
function getSisters(page) {
var start = (page - 1) * 16
var end = page * 16
var sisters = SISTERS.slice(start, end)
return sisters
} -->
<!-- util.js -->
<!-- let bodyWidth = Number(
getComputedStyle(document.body).width.replace("px", ""),
)
let halfBodyWidth = bodyWidth / 2
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)
}
}
img.onload = () => {
const ratio = img.height / img.width
const halfHeight = ratio * halfBodyWidth
// 高度按屏幕一半的比例来计算
heights[index] = halfHeight
checkIfFinished()
}
img.onerror = () => {
heights[index] = 0
checkIfFinished()
}
img.src = imgs[index]
}
imgs.forEach((img, index) => load(index))
})
}
let sum = (nums) => nums.reduce((a, b) => a + b, 0)
let omitByIndexes = (arr, omitIndexes) => {
let res = []
for (let i = 0; i < arr.length; i++) {
if (!omitIndexes.includes(i)) {
res.push(i)
}
}
return res
} -->