ナップサック問題の改良

[synsis]

ナップサック問題を解くプログラムを考えているのですが、
今のままでは重複ありで、出力結果が
品物 1,1,1,1,1,1,
価格 366
となってしまいます。
これを重複なし、つまり品物が被らないようにしたいのですが、どのように書き加えればいいのでしょうか？

コード:

#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define limit 121         // ナップサックの重量制限値
#define n 10             // 品物の種類

struct body 
{
    string name;     // 品名
    int size;       // 重さ 
    int price;     // 価格 
};

int main(void)
{
     // データの格納
     struct body a[10];
     a[0].name="1"; a[0].size=20; a[0].price=61;
     a[1].name="2"; a[1].size=31; a[1].price=89;
     a[2].name="3"; a[2].size=15; a[2].price=32;
     a[3].name="4"; a[3].size=41; a[3].price=47;
     a[4].name="5"; a[4].size=16; a[4].price=18;
	 a[5].name="6"; a[5].size=39; a[5].price=42;
     a[6].name="7"; a[6].size=13; a[6].price=12;
     a[7].name="8"; a[7].size=68; a[7].price=45;
     a[8].name="9"; a[8].size=15; a[8].price=5;
     a[9].name="10"; a[9].size=10; a[9].price=2;
    int value[limit+1];
    string item[limit+1];
     
    for (int s=0; s<=limit; s++)
    {
        value[s]=0;         // 初期値
    }

    for (int i=0; i<n; i++)  // 品物の番号
    {                      
        for (int s=a[i].size; s<=limit; s++)  //  ナップのサイズ
	{
	    int p=s-a[i].size;   // 空きサイズ
            int newvalue=value[p]+a[i].price;

            if (newvalue>value[s])
	    {
	       // 最適解の更新
	       value[s]=newvalue;
	       item[s]=item[p]+a[i].name+",";
            }
        }
    }

    // 表示
    cout << "品物\t" << item[limit] << endl;
    cout << "価格\t" << value[limit] << endl;
}

[milfeulle]

いくつか考えられますが、あえて書き換えるなら【方法1】を提案します。少し変形させて、【方法2】を提案します。最後に実数でも使える【方法3】を提案します。他にも、処理の書き方として再帰を使った書き方もありますし、グラフなどを用いたもっといい方法があるかもしれません。

空きサイズsに対し、最適解value、最適解の文字列itemと定義しているのですね。今回のロジックは、

1. 商品iを選択
2. 選択した上で、すべての空きサイズに対し、現在の価格を最適解として更新
3. iを加算して1.へ。iが上限値に達したら終了
このような2.の処理だと、例えば商品1の場合サイズが20ですから、
空きサイズ20のとき : newvalue = (空きサイズ0のとき) + 20 = 20
空きサイズ40のとき : newvalue = (空きサイズ20のとき) + 20 = 40
となって、更新されてしまいます。問題は空きサイズsのときすでに追加しようとしている商品が存在しているか不明な点ですね。せっかくitemを記録しているのですから、これを探索しやすいようにlist<int>にしておきます。こうすれば、探索もしやすくなります。つまり、newvalueを更新しようとするときに、空きサイズsのときすでに追加していないかチェックし、なければ更新、あったら更新しないようにします。【方法1】

(以下長い余談です)

ただこの方法は毎回探索するコストが掛かりますのであまりよい方法とは思えませんね; value[limit+1]ではなく、商品と対応付けたvalue[n][limit+1]と定義する方法があります。【方法2】この場合、i番目以下の商品からs以下のサイズで選ぶ最大の価格を返します。

例えば、
value[0][0]は0番目以下の商品から0以下のサイズで選ぶ最大の価格を表しますが、そんなものがないので0ですね。value[0][20]は61です。value[0][40]は同じく61です。つまり、value[0]に関してはs>=20においてvalue[0] = 61です。

value[1]について考えてみましょう。value[1][20]は、1番め以下の商品から20以下のサイズで選ぶ最大の価格を表します。次の場合を考えてみます。
(i) s < 31
1番めの商品の大きさは31なので、自動的に0番目以下から選択することとなり、その最大価格はvalue[0]ですね。
(ii) 31 <= s
1番目の商品は選択できる大きさです。ここで選択すべきは、1番目の商品を選択するか否かです。選択した場合、価格は1番目の商品 + 0番目以下の最大となる商品となります。式で表せばa[1].price + value[0][s - a[1].size]です。選択肢なかった場合、価格は0番目以下の最大となる商品のものだけとなり、value[0]となります。どちらか大きい物が最適ということは直感的にわかります。ということは、
value[1] = s < a[1].size ? value[0] : max(a[1].price + value[0][s - a[1].size], value[0]);
と定義できます。

続いてvalue[2][s]について考えてみます。こちらも同様に、商品2を選択するか否かなので、
value[2][s] = s < a[2].size ? value[0][s] : max(a[2].price + value[1][s - a[2].size], value[0][s]);
と定義できます。すなわち、空きサイズがa[2].sizeに満たなければ、商品1以下から最適なものを選択し、そうでなければ、商品2を選択するか、しないかどちらか最適なものを解とするということです。

一般に商品iについて、
value[s] = s < a.size ? value[s] : max(a.price + value[s - a.size], value[0][s]);
が成立することとなります。

結果は

品物 1, 2, 3, 5, 6,
価格 242

だそうです。

オフトピック

こう考えると、よりメモリを使わない方法も考えられます。【方法3】商品0以下では分岐が1つ、それはsがa[0].size未満か否かです。ということは必要な情報は{ 商品0のサイズ, 商品0の価格 }だけです。

商品iを選ぶか選ばないか考えます。商品iを選ぶには、そもそも空きサイズが商品のサイズ以上必要です。とうことで、商品iのサイズ + すべての最適解で調査します。ただし、商品iだけを選ぶ選択肢を用意します。

最適解jは{ サイズj, 価格j }のペアで表されます。サイズj-1以上サイズj未満の場合、価格j-1, サイズj以上サイズj+1未満の場合価格jとなるということです。

すべてのサイズjについて、商品iを選ばなかった場合は、サイズjが引き継がれ最適解は価格jとなります。商品iを選んだ場合は、(サイズj-商品iのサイズ)のときの最適解+商品iの価格となり、選んだ場合と選ばなかった場合の大きいほうが最適解となります。もしも選ばなかった場合が大きければ、変更しません。選んだほうが大きければ、サイズjでの最適解が更新されます。

続いて、サイズj + 商品iのサイズについて考えます。このサイズでも選ぶか選ばないか選択し、最適な方を選びます。

ちょっと冗長ですが実装した結果は次のとおりです(C++11です。コンパイラが対応していない場合は雰囲気だけ掴んでください^^;) :
# これはヒープとか使ったほうがいいですね

コード:

#include <iostream>
#include <string>
#include <list>
#include <vector>
using namespace std;

struct Item {
	int size;
	int price;
	string name;
};

struct Period {
	Period(int size, int price) : size(size), price(price) {}
	int size;
	int price;
};

list<Period> g_periods;

int getMaximumPrice(int size, Period*& period) {
	int ret = 0;
	period = nullptr;

	for(auto it = g_periods.begin(); it != g_periods.end(); ++it) {
		if(size < it->size) {
			return ret;
		}
		ret = it->price;
		period = &*it;
	}
	return ret;
}

int getMaximumPrice(int size) {
	int ret = 0;

	for(auto it = g_periods.begin(); it != g_periods.end(); ++it) {
		if(size < it->size) {
			return ret;
		}
		ret = it->price;
	}
	return ret;
}

void insertPeriod(Period period, int max_size) {
	if(period.size > max_size) {
		return;
	}

	auto it = g_periods.begin();
	for(; it != g_periods.end(); ++it) {
		if(period.size < it->size) {
			g_periods.insert(it, period);
			return;
		}
		else if(period.size == it->size) {
			return;
		}
	}
	g_periods.insert(it, period);
}

int main() {
	Item items[] = {
		{20, 61, "1"},
		{31, 89, "2"},
		{15, 32, "3"},
		{41, 47, "4"},
		{16, 18, "5"},
		{39, 42, "6"},
		{13, 12, "7"},
		{68, 45, "8"},
		{15, 5, "9"},
		{10, 2, "10"}
	};
	int length = sizeof(items) / sizeof(items[0]);
	int max_size = 121;

	g_periods.emplace_back(items[0].size, items[0].price);

	for(int i = 1; i < length; ++i) {
		int size = items[i].size;
		int price = items[i].price;
		list<Period> add_list; 
		
		if(price > getMaximumPrice(size)) {
			add_list.emplace_back(size, price);
		}
		
		for(auto it = g_periods.begin(); it != g_periods.end(); ++it) {
			Period* period_selected;
			int price_selected = price + getMaximumPrice(it->size - size, period_selected);
			int price_notselected = getMaximumPrice(it->size);
			
			if(price_selected > price_notselected) {
				if(period_selected) {
					period_selected->price = price_selected;
				}
			}

			price_selected = price + getMaximumPrice(it->size);
			price_notselected = getMaximumPrice(it->size + size);

			if(price_selected > price_notselected) {
				add_list.emplace_back(it->size + size, price_selected);
			}
			else {
				add_list.emplace_back(it->size + size, price_notselected);
			}
		}

		for(auto it = add_list.begin(); it != add_list.end(); ++it) {
			insertPeriod(*it, max_size);
		}
	}

	for(auto it = g_periods.begin(); it != g_periods.end(); ++it) {
		cout << "(" << it->size << ", " << it->price << ")" << ",";
	}

	cin.get();
}

[かずま]

再帰を使うと簡単ですね。

コード:

#include <iostream>
#include <string>
 
using namespace std;
 
#define LIMIT 121  // ナップサックの重量制限値
#define N 10       // 品物の種類
 
struct Body 
{
    string name;   // 品名
    int size;      // 重さ 
    int price;     // 価格 
};
 
Body a[N] = {
    { "1",  20, 61 },
    { "2",  31, 89 },
    { "3",  15, 32 },
    { "4",  41, 47 },
    { "5",  16, 18 },
    { "6",  39, 42 },
    { "7",  13, 12 },
    { "8",  68, 45 },
    { "9",  15,  5 },
    { "10", 10,  2 },
};

int b[N], max_b[N];
int max_value;

void step(int i, int size, int value)
{
    if (size > LIMIT) return;
    if (i < N) {
        b[i] = 1; step(i + 1, size + a[i].size, value + a[i].price);
        b[i] = 0; step(i + 1, size, value);
    }
    else {
        if (value > max_value) {
            max_value = value;
            for (int i = 0; i < N; i++) max_b[i] = b[i];
        }
    }
}

int main()
{
    step(0, 0, 0); 
    cout << "品物\t";
    for (int i = 0; i < N; i++)
        if (max_b[i]) cout << a[i].name << ',';
    cout << "\n価格\t" << max_value << endl;
}

実行結果

コード:

品物	1,2,3,5,6,
価格	242

理解できたら、何をやっているのか言葉で説明してください。
理解できなければ、何がわからないのか質問してください。

[かずま]

再帰を使わず、ビット演算でやると、

コード:

#include <iostream>
#include <string>
 
using namespace std;
 
#define LIMIT 121  // ナップサックの重量制限値
#define N 10       // 品物の種類
 
struct Body {
    string name;   // 品名
    int size;      // 重さ 
    int price;     // 価格 
};
 
Body a[N] = {
    { "1",  20, 61 },
    { "2",  31, 89 },
    { "3",  15, 32 },
    { "4",  41, 47 },
    { "5",  16, 18 },
    { "6",  39, 42 },
    { "7",  13, 12 },
    { "8",  68, 45 },
    { "9",  15,  5 },
    { "10", 10,  2 },
};

int main()
{
    int b, max_b = 0, max_value = 0;
    for (b = 0; b < (1<<N); b++) {
        int i, size = 0, value = 0;
        for (i = 0; i < N; i++)
            if (b & (1<<i)) {
                size += a[i].size;
                if (size > LIMIT) break;
                value += a[i].price;
            }
        if (i == N && value > max_value)
            max_value = value, max_b = b;
    }
    cout << "品物\t";
    for (int c = 0, i = 0; i < N; i++)
        if (max_b & (1<<i))
            c && cout << ',', cout << a[i].name, c = 1;
    cout << "\n価格\t" << max_value << endl;
}