迭代以找出不同数量元素的组合

Question

我正在编写一个程序，使用动态规划来决定如何将一些文件（电影）分配到DVD上，以使用最少的DVD。经过深思熟虑，我决定一个好的方法是查看每种可能的电影组合，其大小不超过4.38 GB（实际DVD的大小），并选择最大的组合（即浪费空间最少的那个），然后以最有效的组合删除电影，并重复此过程，直到运行完所有电影。

问题是，我不知道如何循环以找出每种可能的组合，因为电影的大小各不相同，无法使用特定数量的嵌套循环。

伪代码：

Some kind of loop:
    best_combination=[]
    best_combination_size=0
    if current_combination<4.38 and current_combination>best_combination_size:
        best_combination=current_combination
        best_combination_size=best_combination_size
print(best_combination)
delete best_combination from list_of_movies

第一次发布问题...所以请大家温柔点！！提前感谢。

P.S. 我想出了一种用Dijkstra算法来完成的方法，我认为这样会很快，但不太友好。如果有人感兴趣，我很乐意讨论。

- Mazen Sharkawy

---

你提出的是一种启发式方法而不是全局优化解。如果你能接受这一点，坚持使用常见的装箱启发式方法会更容易。维基百科上的“bin-packing”文章也应该指导你使用最优动态规划方法（但我不会使用；我会从启发式方法开始）。 - sascha

另外值得一提的是，由于Dijkstra算法属于P问题，而这个问题属于NP问题，你的想法实现起来非常不可能（找到最优解；甚至选择所有电影；尽可能填满一张DVD等）。 - sascha

谢谢Sascha。那么你建议什么是“全局最优解”？ - Mazen Sharkawy

基于动态规划的方法（针对整个问题，而非填充DVD之后）可能有效。基于混合整数规划的方法可能会更好（经过调整）。但由于它是NP完全问题，理论上总会出现棘手的实例。 - sascha

大约有多少电影总数？此外，最佳打包的DVD和未最佳打包的DVD之间的一个例子差异是什么（例如有多少电影）？另外，电影长度的分布情况是什么（例如有多少部电影约为90分钟，有多少部电影约为120分钟等），以及一张DVD可以容纳多少分钟的电影？此外，在将电影打包到一张DVD中时，长度是否是唯一考虑的特征？ - גלעד ברקן

Answer 1

您应该坚持使用常见的装箱启发式算法。维基百科文章概述了包括链接在内的方法，适用于特定问题的确切方法。但请始终记住：这是一个NP完全问题！

我将向您展示一些支持我的提示的示例，即您应该坚持使用启发式算法。

以下Python代码：

• 创建参数化随机问题（多个平均值/标准差的正态分布；接受抽样以确保没有电影比DVD大）
• 使用某些实现某些贪婪启发式的随机装箱库（我之前没有尝试或测试过此库；因此不提供任何保证！;不知道使用哪种启发式算法）
• 使用朴素的混合整数规划实现（由商业求解器解决；开源求解器如cbc会遇到困难，但可以用于良好的近似解）

代码

import numpy as np
from cvxpy import *
from time import time

""" Generate some test-data """
np.random.seed(1)
N = 150  # movies
means = [700, 1400, 4300]
stds = [100, 300, 500]
DVD_SIZE = 4400

movies = []
for movie in range(N):
    while True:
        random_mean_index = np.random.randint(low=0, high=len(means))
        random_size = np.random.randn() * stds[random_mean_index] + means[random_mean_index]
        if random_size <= DVD_SIZE:
            movies.append(random_size)
            break

""" HEURISTIC SOLUTION """
import binpacking
start = time()
bins = binpacking.to_constant_volume(movies, DVD_SIZE)
end = time()
print('Heuristic solution: ')
for b in bins:
    print(b)
print('used bins: ', len(bins))
print('used time (seconds): ', end-start)

""" Preprocessing """
movie_sizes_sorted = sorted(movies)
max_movies_per_dvd = 0
occupied = 0
for i in range(N):
    if occupied + movie_sizes_sorted[i] <= DVD_SIZE:
        max_movies_per_dvd += 1
        occupied += movie_sizes_sorted[i]
    else:
        break

""" Solve problem """
# Variables
X = Bool(N, N)  # N * number-DVDS
I = Bool(N)     # indicator: DVD used

# Constraints
constraints = []
# (1) DVDs not overfilled
for dvd in range(N):
    constraints.append(sum_entries(mul_elemwise(movies, X[:, dvd])) <= DVD_SIZE)
# (2) All movies distributed exactly once
for movie in range(N):
    constraints.append(sum_entries(X[movie, :]) == 1)
# (3) Indicators
for dvd in range(N):
    constraints.append(sum_entries(X[:, dvd]) <= I[dvd] * (max_movies_per_dvd + 1))

# Objective
objective = Minimize(sum_entries(I))

# Problem
problem = Problem(objective, constraints)
start = time()
problem.solve(solver=GUROBI, MIPFocus=1, verbose=True)
#problem.solve(solver=CBC, CliqueCuts=True)#, GomoryCuts=True, KnapsackCuts=True, verbose=True)#, GomoryCuts=True, MIRCuts=True, ProbingCuts=True,
              #CliqueCuts=True, FlowCoverCuts=True, LiftProjectCuts=True,
              #verbose=True)
end = time()

""" Print solution """
for dvd in range(N):
    movies_ = []
    for movie in range(N):
        if np.isclose(X.value[movie, dvd], 1):
            movies_.append(movies[movie])
    if movies_:
        print('DVD')
        for movie in movies_:
            print('     movie with size: ', movie)

print('Distributed ', N, ' movies to ', int(objective.value), ' dvds')
print('Optimizatio took (seconds): ', end-start)

部分输出

Heuristic solution:
-------------------
('used bins: ', 60)
('used time (seconds): ', 0.0045168399810791016)

MIP-approach:
-------------
Root relaxation: objective 2.142857e+01, 1921 iterations, 0.10 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   21.42857    0  120  106.00000   21.42857  79.8%     -    0s
H    0     0                      68.0000000   21.42857  68.5%     -    0s
H    0     0                      63.0000000   21.42857  66.0%     -    0s
     0     0   21.42857    0  250   63.00000   21.42857  66.0%     -    1s
H    0     0                      62.0000000   21.42857  65.4%     -    2s
     0     0   21.42857    0  256   62.00000   21.42857  65.4%     -    2s
     0     0   21.42857    0  304   62.00000   21.42857  65.4%     -    2s
     0     0   21.42857    0  109   62.00000   21.42857  65.4%     -    3s
     0     2   21.42857    0  108   62.00000   21.42857  65.4%     -    4s
    40     2   27.61568   20   93   62.00000   27.61568  55.5%   110    5s
H  156    10                      61.0000000   58.00000  4.92%  55.3    8s
   262     4   59.00000   84   61   61.00000   59.00000  3.28%  44.2   10s
   413    81 infeasible  110        61.00000   59.00000  3.28%  37.2   15s
H  417    78                      60.0000000   59.00000  1.67%  36.9   15s
  1834  1212   59.00000  232   40   60.00000   59.00000  1.67%  25.7   20s
...
...
 57011 44660 infeasible  520        60.00000   59.00000  1.67%  27.1  456s
 57337 44972   59.00000  527   34   60.00000   59.00000  1.67%  27.1  460s
 58445 45817   59.00000   80   94   60.00000   59.00000  1.67%  26.9  466s
 59387 46592   59.00000  340   65   60.00000   59.00000  1.67%  26.8  472s

分析

对上面的例子进行一些观察：

• 启发式算法立即获得价值为60的一些解决方案
• 商业求解器需要更多时间，但也找到了价值为60的解决方案（15秒）
  • 也试图找到更好的解决方案或证明不存在（MIP求解器是完整的=在无限时间内找到最优解决方案或证明不存在！）
  • 有一段时间没有进展！
  • 但是：我们已经证明，最佳情况下只有一个大小为59的解决方案
  • = 也许通过最优解决问题可以节省一张DVD；但很难找到解决方案，我们不知道这个解决方案是否存在（尚未确定！）

备注

以下观察结果严重依赖于数据统计

可以尝试其他问题（可能更小），商业MIP求解器找到的解决方案使用1个较少的DVD很容易（例如49 vs. 50）

不值得（记住：开源求解器甚至更难）

公式非常简单，没有调整（不要只责怪求解器）

有确切的算法（可能更复杂），可能是适当的

结论

通常启发式方法易于实现并且提供非常好的解决方案。大多数这些方法还具有非常好的理论保证（例如，与最优解相比最多使用11/9 opt + 1 #DVD =首次递减启发式）。尽管我通常对优化很感兴趣，但在这里我可能会使用启发式方法。

一般问题也非常流行，因此在许多编程语言中应该存在某些很好的库用于此问题！

- sascha

---

谢谢你的回答。你做得很好地解释了它，而且在格式和结构上做得更好。我想知道你是从哪里学习启发式算法和NP问题的？ - Mazen Sharkawy

@MazenSharkawy 嗯，我是一名计算机科学专业的学生，在大学学习了基本的算法知识以及一些关于复杂性理论的高级课程（扩展图仍然让我做噩梦）。在过去的几年里，我更加关注数学优化（有时与机器学习很好地结合），我部分地在大学学习了这方面的知识，但更高级的内容则是通过可用的大学课程学习的（特别是斯坦福大学的 Stephen Boyds 组）。感谢你的美言！ - sascha

Answer 2

不要声称这个答案提供的解决方案是优化的、最佳的或拥有任何其他显著的特点，这里提出了一种贪心方法来解决 DVD 包装问题。

import System.Random
import Data.List
import Data.Ord

-- F# programmers are so used to this operator, I just cannot live without it ...yet.
(|>) a b = b a 
data Dvd = Dvd { duration :: Int, movies :: [Int] } deriving (Show,Eq)

dvdCapacity = 1000 :: Int -- a dvd has capacity for 1000 time units - arbitrary unit
-- the duration of a movie is between 1 and 1000 time units
r = randomRs (1,1000) (mkStdGen 42) :: [Int] 
-- our test data set of 1000 movies, random movie durations drawn from r
allMovies = zip [1..1000] (take 1000 r)     
allMoviesSorted = reverse $ sortBy (comparing snd) allMovies
remainingCapacity dvd = dvdCapacity - duration dvd

emptyDvd = Dvd { duration = 0, movies = [] }

-- from the remaining movies, pick the largest one with at most maxDuration length.
pickLargest remaining maxDuration =
    let (left,right) = remaining |> break (\ (a,b) -> b <= maxDuration)
        (h,t) = case right of 
            [] -> (Nothing,[]) 
            otherwise -> (Just (head right), right |> tail)
        in 
            (h,[left, t] |> concat)

-- add a track (movie) to a dvd
addTrack dvd track = 
    Dvd {duration = (duration dvd) + snd track, 
        movies = fst track : (movies dvd) }

-- pick dvd from dvds with largest remaining capacity 
-- and add the largest remaining fitting track
greedyPack movies dvds 
    | movies == [] = (dvds,[])
    | otherwise =

        let dvds' = reverse $ sortBy (comparing remainingCapacity) dvds
            (picked,movies') =
                case dvds' of
                    [] -> (Nothing, movies)
                    (x:xs) -> pickLargest movies (remainingCapacity x)
            in
                case picked of
                    Nothing ->
                        -- None of the current dvds had enough capacity remaining
                        -- tp pick another movie and add it. -> Add new empty dvd
                        -- and run greedyPack again. 
                        greedyPack movies' (emptyDvd : dvds')
                    Just p ->
                        -- The best fitting movie could be added to the 
                        -- dvd with the largest remaining capacity.
                        greedyPack movies' (addTrack (head dvds') p : tail dvds')   

(result,residual) = greedyPack allMoviesSorted [emptyDvd] 
usedDvdsCount = length result
totalPlayTime = allMovies |> foldl (\ s (i,d) -> s + d) 0
optimalDvdsCount = round $ 0.5 + fromIntegral totalPlayTime / fromIntegral dvdCapacity
solutionQuality = length result - optimalDvdsCount

与理论最优DVD数量相比，它在给定数据集上浪费了4个额外的DVD。

- BitTickler