題目：

有很多隨機大小的明信片，也有很多隨機大小的信封。希望把一個明信片裝到多個信封里。明信片只能裝入比自己大的信封，信封也只能裝入更大的信封。相同的大小無法裝入。

為了保證最大數量的信封被使用，請設計演算法。

解決方法

1.將明信片和信封各自排序。

2.找到第一個明信片。

3.找到沒使用的第一個信封。

4. 是否可裝入，是則裝入。否按順序向前從大到小找卡片，能裝入則裝入。不能裝入則繼續從大到小找卡片。直到沒有卡片可找。

代碼

package sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NestedEnvelope {

public static void main(String[] args) {
List<Card> cards = new ArrayList<>;
for (int i = 0; i < 5; ++i) {
Card card = new Card;
card.size = i * 2;
card.id = i;
cards.add(card);
}

List<Envelop> evelops = new ArrayList<>;

for (int i = 0; i < 10; ++i) {
Envelop env = new Envelop;
env.size = i;
env.id = i;
evelops.add(env);
}

HashMap<Card, List<Envelop>> results = putInCard(cards, evelops);

for (Map.Entry<Card, List<Envelop>> entry : results.entrySet) {
System.out.println("[");
System.out.println("card:" + entry.getKey.size);
for (Envelop env : entry.getValue) {
System.out.println("envelop:" + env.size);
}
System.out.println("]");
}
}

static class Card implements Comparable<Card> {
int id;
int size;

@Override
public int compareTo(Card o) {
// TODO Auto-generated method stub
return size - o.size;
}
}

static class Envelop implements Comparable<Envelop> {
int id;
int size;

@Override
public int compareTo(Envelop o) {
// TODO Auto-generated method stub
return size - o.size;
}
}

public static HashMap<Card, List<Envelop>> putInCard(List<Card> cards, List<Envelop> envelops) {

Collections.sort(cards);

Collections.sort(envelops);

HashMap<Card, List<Envelop>> cardWithEnvelops = new HashMap<Card, List<Envelop>>;

for (int i = 0; i < cards.size; ++i) {

Card card = cards.get(i);

Card nextCard = null;

if (i + 1 < cards.size) {
nextCard = cards.get(i + 1);
}

List<Envelop> cardEnvelops = new ArrayList<Envelop>;

cardWithEnvelops.put(card, cardEnvelops);

Envelop lastEnvelop = null;

while (envelops.size > 0) {

Envelop envelop = envelops.get(0);

if ((lastEnvelop != null && envelop.size == lastEnvelop.size) || envelop.size == card.size) {

for (int indexCard = i - 1; indexCard >= 0; --indexCard) {

List<Envelop> preEnvelops = cardWithEnvelops.get(cards.get(indexCard));

if (preEnvelops.size == 0) {

preEnvelops.add(envelop);

} else {

Envelop maxEnv = preEnvelops.get(preEnvelops.size - 1);

if (maxEnv.size < envelop.size) {

preEnvelops.add(envelop);
}
}
}

envelops.remove(envelop);

continue;
}

if (envelop.size > card.size && (nextCard == null || envelop.size <= nextCard.size)) {

cardEnvelops.add(envelop);

lastEnvelop = envelop;

envelops.remove(envelop);

} else {
break;
}
}
}
return cardWithEnvelops;
}
}

列印：

[
card:4
envelop:5
envelop:6
]
[
card:8
envelop:9
]
[
card:0
envelop:1
envelop:2
]
[
card:2
envelop:3
envelop:4
]
[
card:6
envelop:7
envelop:8
]

總結：

結果並不是只有一種裝法最多，但是只要保證是裝的信封最多。

因此，此題目演算法不止一種。可能還有其他演算法，以後再具體分析。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！