請教 - 多組數字挑選加總為指定數值的方法

wenwenwen
個人積分：87分
文章編號：44664321

87分

樓主

2013-06-28 22:30

公司的產品，因生產良率的緣故每包的內裝數量是不定的。數量範圍約在 200-5000 間。
生產完每包都封好送去庫房。

接到客戶下的訂單後(一般都是下整數的數量，如2000, 10000 等)，
倉庫的同事就用手工的方法去由這些產品包上的數量拼湊加總出要出貨的數量
(要大於等於客戶訂單數的最小數量)。

公司倉庫的私下決定是只要不超過 1% 的數量就可以。

三位的庫房同事，有一位非常厲害，幾乎每次都能達成完全符合的情形。

我認為這個數量的挑選加總來達到指定數量，應是可以用電腦輔助來達成的。

目前我只能想到用窮舉法 C(n,m)，在挑貨組合破千包的情形下，用窮舉法跟本天文數字。

可否請教各位前輩給個方向。謝謝您。

下圖舉例 20 組數字，目標要挑出加總為 10000 的組合。
我用手工挑出了 2 組『自認』為最接近的。

688
1192
891
803
1059
1077
1372
561
740
1466
516
715
1379
1467
1137
820
528
1330
797
1401

不想唸物理了...

2013-06-28 22:30 發佈

snare

snare
個人積分：979分
文章編號：44685738

979分

2樓

2013-06-30 11:44

數量少的話，勉強可以用公式解決

像您這種問題，要用vba

另一個方式可以用 “規劃求解” 增益集(excel 內建)

規劃求解 + sumproduct() + 設定格式化條件
(可以自動標示出需要的數值)
不過還是有一些限制，要出門了，有空再解釋

算出來的答案 (10000)
688
1192
561
1466
516
1379
1467
1330
1401

算出來的答案 (10001)
688
1192
561
740
715
1379
1467
528
1330
1401

wenwenwen

wenwenwen
個人積分：87分
文章編號：44691409

87分

樓主

2013-06-30 19:29

我舉這例子時是用亂數取個20組，沒想到裏面真的可以拼出想要的目標10000數字。

再請您給個思考方向吧。

謝謝您。

不想唸物理了...

wenwenwen

wenwenwen
個人積分：87分
文章編號：44691702

87分

樓主

2013-06-30 19:54

snare大您好，

剛才試了下 Excel 的規劃求解，真的可以算出來呢。

不過它也算了超過10000次以上才找到結果。

1077
740
516
715
1467
1137
820
1330
797
1401

不想唸物理了...

wenwenwen

wenwenwen
個人積分：87分
文章編號：44692584

87分

樓主

2013-06-30 20:58

目前思考的方向如下，

20組數字，挑選其中來組成目標數 10000。

1. 20組數字先進行排序
516,528,561,688,715,740,797,803,820,891,1059,1077,1137,1192,1330,1372,1379,1401,1466,1467

2. 由小加到大，到第 13 組破目標值 10000。

3. 由大加到小，到第 8 組破目標值 10000。

4. 使用排列組合 20挑8,20挑9,20挑10,20挑11,20挑12,20挑13 的各種來嘗試達到目標數。總共有 850,136 種組合。

不想唸物理了...

snare

snare
個人積分：979分
文章編號：44692875

979分

6樓

2013-06-30 21:16

wenwenwen wrote:
剛才試了下 Excel 的規劃求解，真的可以算出來呢。
不過它也算了超過10000次以上才找到結果。...(恕刪)

20選9，不考慮總合，只單純用機率來算，有6906900種不同組合方式
如果是 50選9，10648873950 種組合方式
10000次，算快了

==========================================================
找出最接近或等於的方式

一、目標儲存格的公式改成 =abs(sumproduct(資料範圍)-想要的最大數字)

二、限制式那邊，只留一個，改成 = binary

三、線性模式=>不要選，採用非負值=>不要選

四、把 "等於：" 那邊，改選 "最小值"

wenwenwen

wenwenwen
個人積分：87分
文章編號：44693036

87分

樓主

2013-06-30 21:24

Dear snare 前輩，

20選9 有 690 萬種是排列+組合的結果。
如果像我這種需求只要組合不需排列，只要 167960 組合。這樣電腦用窮舉法還可以接受的吧。

snare wrote:
20選9，不考慮總合，只單純用機率來算，有6906900種不同組合方式...(恕刪)

不想唸物理了...

snare

snare
個人積分：979分
文章編號：44693056

979分

8樓

2013-06-30 21:26

wenwenwen wrote:
這樣電腦用窮舉法還可以接受的吧...(恕刪)

不管怎麼說，都比人腦快吧

又要出門了，有空再解釋

yinhell

yinhell
個人積分：15分
文章編號：44696562

15分

9樓

2013-07-01 0:15

wenwenwen wrote:
公司的產品，因生產良...(恕刪)

入倉前
688
1192
891
803
1059
1077
1372
561
740
1466
516
715
1379
1467
1137
820
528
1330
797
1401

排大小後

516
528
561
688
715
740
797
803
820
891
1059
1077
1137
1192
1330
1372
1379
1401
1466
1467

以1000為基準處理一下

1st 516 - 1000 = -484
2nd 528 - 1000 = -472
3rd 561 - 1000 = -439
4th 688 - 1000 = -312
5th 715 - 1000 = -285
6th 740 - 1000 = -260
7th 797 - 1000 = -203
8th 803 - 1000 = -197
9th 820 - 1000 = -180
10th 891 - 1000 = -109
11th 1059 - 1000 = 59
12th 1077 - 1000 = 77
13th 1137 - 1000 = 137
14th 1192 - 1000 = 192
15th 1330 - 1000 = 330
16th 1372 - 1000 = 372
17th 1379 - 1000 = 379
18th 1401 - 1000 = 401
19th 1466 - 1000 = 466
20th 1467 - 1000 = 467

每一組正負的組合差不多略大於0, 也就是說剛好2000出頭

出貨2000
ex1 192 - 180 = 12
=> 14th + 9th

ex2 330 - 312 = 18 --> 公司多付出成本
=> 15th + 4th

2正1負或1正2負相加略大於0, 可以出貨3000

出貨3000
ex1: 59 + 77 - 109 = 34
=> 11th + 12th + 10th

ex2: 401 - 197 - 203 = 1 --> 公司省出貨成本
=> 18th + 7th + 8th

要出貨4000,可以考慮3+1- or 2+2- or 1+3-

其他數量可依此類推...

入倉前先前置作業一下，出貨就簡單了。

(若數字算錯，請見諒)

wenwenwen

wenwenwen
個人積分：87分
文章編號：44698605

87分

樓主

2013-07-01 7:03

謝謝 yinhell 大的經驗分享，

我提出的例子是 20 組，實際作業時一般為 500-1000 組

所以之前思維被卡住就是這樣的組合數是天文數字，還要加上先進先出等其他小出貨原則，給有經驗的同事手挑還比較快。他們都可在10-15分鐘左右挑出個結果來。

預先分組將數字組合(像您的例子是2個配對)，再來進行組合真是很棒的想法，
我來寫成程式試看看。看要分幾個數字一組+多層次組合會比較好。

yinhell wrote:
入倉前6881192...(恕刪)

不想唸物理了...