組合せ最適化 – サブセットから合計がターゲット値に最も近い組み合わせを求める

Find nearest value to a target with a given set of values where repetition is allowed – StackOverflow

!pip install -q pulp
import pulp
 

def soln(S, t, printing=True):
    var = [pulp.LpVariable(f'var{i}', 0, cat='Integer') for i in range(len(S))]
    p = pulp.LpProblem('The greatest sum, equal or smaller to t', pulp.LpMaximize)
    p += pulp.lpDot(var, S) - pulp.lpSum(var)
    p += pulp.lpDot(var, S) <= t
    ss = p.solve()
    print(p)
    print(f'Status: {pulp.LpStatus[ss]}', end='\n\n')
    if printing:
        res = [x.varValue for x in var]
        print('*** Result ***')
        print(f'Total: {p.objective.value()+sum(res)}')
        print(res, end='\n\n')
    else:
        return p


Slst = ([500, 1000, 2000, 5000], [500, 1000, 2000, 5000], [222,333])
tlst = (7000, 7990, 444)
for S, t in zip(Slst, tlst):
    print(f'Given values: {S}, Target: {t}', end='\n\n')
    soln(S, t)
Given values: [500, 1000, 2000, 5000], Target: 7000

The greatest sum, equal or smaller to t:
MAXIMIZE
499*var0 + 999*var1 + 1999*var2 + 4999*var3 + 0
SUBJECT TO
_C1: 500 var0 + 1000 var1 + 2000 var2 + 5000 var3 <= 7000

VARIABLES
0 <= var0 Integer
0 <= var1 Integer
0 <= var2 Integer
0 <= var3 Integer

Status: Optimal

*** Result ***
Total: 7000.0
[0.0, 0.0, 1.0, 1.0]

Given values: [500, 1000, 2000, 5000], Target: 7990

The greatest sum, equal or smaller to t:
MAXIMIZE
499*var0 + 999*var1 + 1999*var2 + 4999*var3 + 0
SUBJECT TO
_C1: 500 var0 + 1000 var1 + 2000 var2 + 5000 var3 <= 7990

VARIABLES
0 <= var0 Integer
0 <= var1 Integer
0 <= var2 Integer
0 <= var3 Integer

Status: Optimal

*** Result ***
Total: 7500.0
[1.0, 0.0, 1.0, 1.0]

Given values: [222, 333], Target: 444

The greatest sum, equal or smaller to t:
MAXIMIZE
221*var0 + 332*var1 + 0
SUBJECT TO
_C1: 222 var0 + 333 var1 <= 444

VARIABLES
0 <= var0 Integer
0 <= var1 Integer

Status: Optimal

*** Result ***
Total: 444.0
[2.0, 0.0]
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください