階層的クラスタリングツリーがあります（リンケージを使用）。各クラスターには、そのクラスターのコストに対応する樹状図の独自のレベルがあります。コストc1のn1クラスター、コストc2のn2クラスター、およびコストc3のn3クラスターの予算があります。問題は、予算を使用してすべての元のアイテムをカバーするクラスターを選択することです。およびc1>c2>c3。コストc1のクラスターは、明らかにc2またはc3クラスターに使用できます。
予算カテゴリが1つしかない場合、解決策は簡単です。ルートから開始し、c1の下に移動するときに各サブツリーに追加します。サブツリーの前にn1カテゴリが終了した場合、解決策はありません。
2つのカテゴリの場合も簡単です。c1コストのすべての候補を検索します。それらにc2サブクラスターの数でラベルを付け、降順で並べ替えます。ラベルが最大のc1カテゴリを選択します。次に、c2クラスターを選択します。
ただし、c2カテゴリの並べ替えは必ずしもc3予算を追跡するとは限らないため、2つ以上のカテゴリの場合は問題が複雑になります。