直接開始問題达箍，前端開發(fā)過程中我們經(jīng)常會遇到這樣的問題，我們需要在一個寬度固定的區(qū)域顯示一些長度不固定的標簽或者按鈕。
畫個圖說明一下
這是一種看著比較舒服的情況，當然因為每個標簽的長度不固定也有可能出現(xiàn)其他的情況
由于第一行已經(jīng)沒有足夠的空間用來填充接下來的標簽太颤，因此只能把這個位置空出來換一行接著填充苞俘，依次處理盹沈，右邊就會多出很多空白的區(qū)域不能利用。
在不考慮標簽顯示順序的情況下吃谣，有沒有一種辦法能讓整個區(qū)域填充的飽滿一點乞封，也就是右側空白區(qū)域盡可能的小。
我們把這個問題簡單抽象一下：定義整個顯示區(qū)域的寬度為W岗憋；每個Tag的寬度為wi肃晚；是否選取某個Tag為xi={0,1}
針對于每一行要求：
期望：
能夠達到最大
經(jīng)過抽象之后問題就變得明朗了，典型的一種組合優(yōu)化的NP完全問題仔戈，再具體一點就是0-1背包問題
背包問題有很多種求解方式关串，這里選擇一種動態(tài)規(guī)劃的解法拧廊。
背包問題：給定 n 種物品和一個容量為C的背包，物品 i 的重量是 wi晋修，其價值為 vi 吧碾。
應該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大墓卦？
面對每個物品倦春，我們只有選擇拿取或者不拿兩種選擇，不能選擇裝入某物品的一部分落剪，也不能裝入同一物品多次
聲明一個 大小為 m[n][c] 的二維數(shù)組睁本，m[ i ][ j ] 表示 在面對第 i 件物品，且背包容量為 j 時所能獲得的最大價值 忠怖，那么我們可以很容易分析得出 m[i][j] 的計算方法呢堰，
-
j < w[i]的情況，這時候背包容量不足以放下第 i 件物品凡泣，只能選擇不拿
m[ i ][ j ] = m[ i-1 ][ j ] -
j>=w[i]的情況暮胧，這時背包容量可以放下第i件物品，我們就要考慮拿這件物品是否能獲取更大的價值问麸。
如果拿取往衷，m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 這里的 m[ i-1 ][ j-w[ i ] ]指的就是考慮了i-1件物品严卖，背包容量為j-w[i]時的最大價值席舍，也是相當于為第i件物品騰出了w[i]的空間。
如果不拿哮笆，m[ i ][ j ] = m[ i-1 ][ j ] , 同（1）
究竟是拿還是不拿来颤，自然是比較這兩種情況那種價值最大
由此可以得到狀態(tài)轉移方程：
if(j>=w[i])
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
m[i][j]=m[i-1][j];
針對于我們這里的問題vi=wi，我們期待的背包物品的價值就是物品的重量稠肘，具體算法實現(xiàn)
/**
背包算法
@param vws 價值&重量輸入(每個Tag的寬度)
@param width 背包容量(每行Tag能占用的最大寬度)
@return 背包內容物品選擇情況(Tag的選擇情況)
*/
- (NSIndexSet *)backpack:(NSArray<NSNumber *> *)vws width:(NSInteger)width
{
// 背包可選擇物品數(shù)量
int n = (int)vws.count;
// 背包容量
int c = (int)width;
// 物品價值數(shù)組
int *v = malloc(sizeof(int) * (n + 1));
// 物品重量數(shù)組
int *w = malloc(sizeof(int) * (n + 1));
// 初始化價值數(shù)組和重量數(shù)組
*v = 0;
*w = 0;
int *vh = v;
int *wh = w;
for (int i = 0; i < n; i++) {
*++vh = [vws[i] intValue];
*++wh = [vws[i] intValue];
}
// 構造二維轉移矩陣福铅，并初始化為0
int **m = (int **)malloc(sizeof(int *) * (n + 1));
for(int i = 0; i < n + 1; i++) {
*(m + i) = (int *)malloc(sizeof(int) * (c + 1));
for (int j = 0; j < c + 1; j++) {
*(*(m + i) + j) = 0;
}
}
// 構造轉移矩陣
for(int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j >= w[i]) {
m[i][j] = MAX(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
}else {
m[i][j] = m[i - 1][j];
}
}
}
// 標記物品選擇情況
int *x = malloc(sizeof(int) * (n + 1));
for(int i = n; i > 1; i--) {
if(m[i][c] == m[i-1][c]) {
x[i] = 0;
}else {
x[i] = 1;
c-= w[i];
}
}
x[1] = (m[1][c] > 0) ? 1 : 0;
// 返回物品選擇情況
NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];
for (int i = 1; i <= n; i++) {
if (x[i] == 1) {
[indexSet addIndex:i - 1];
}
}
// 回收資源
free(v);
free(w);
free(x);
for(int i = 0; i < n; i++) {
free(*(m + i));
}
return indexSet;
}
在求得了轉移矩陣之后還需要知道具體是選擇了哪個物品，另起一個 x[ ] 數(shù)組项阴，x[i]=0表示不拿滑黔，x[i]=1表示拿。m[n][c]為最優(yōu)值环揽，如果m[n][c]=m[n-1][c] ,說明有沒有第n件物品都一樣略荡，則x[n]=0 ; 否則 x[n]=1。當x[n]=0時歉胶，由x[n-1][c]繼續(xù)構造最優(yōu)解汛兜；當x[n]=1時，則由x[n-1][c-w[i]]繼續(xù)構造最優(yōu)解通今。以此類推粥谬，可構造出所有的最優(yōu)解肛根。
// 標記物品選擇情況
int *x = malloc(sizeof(int) * (n + 1));
for(int i = n; i > 1; i--) {
if(m[i][c] == m[i-1][c]) {
x[i] = 0;
}else {
x[i] = 1;
c-= w[i];
}
}
x[1] = (m[1][c] > 0) ? 1 : 0;
// 返回物品選擇情況
NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];
for (int i = 1; i <= n; i++) {
if (x[i] == 1) {
[indexSet addIndex:i - 1];
}
}
完整代碼參考：
https://github.com/fuxiaoghost/BackpackAlgorithm
我們看看最終完成的效果，雖然丑了點漏策，但是效果還不錯
