در مسئله های روز دنیا قسمتی از مسائل را می‌توانیم به صورت خیلی ابتدایی حل کنیم یعنی به این صورت که تمامی حالات ممکنه را بررسی کنیم و سپس به جواب مورد نظر برسیم که به این روش، کورکورانه یا Blind گفته می شود. برای اینکه بتوانیم تمامی حالات ممکنه را بررسی کنیم می توانیم از ساختار داده ای به نام BitString استفاده کنیم.
در مسئله کوله پشتی یا Knapsack Binary محدودیت که اعمال شده است این است که ما از یک وسیله یا برداریم و یا بر نداریم. برای اینکه بتوانیم تمامی حالات را برای روش Blind تولید کنیم به تعداد اجسام که داریم آرایه را تولید می کنیم که شامل 0 به منظور بر نداشتن و 1 به منظور برداشتن جسم است. حال می خواهیم حالت های مختلف را تولید کنیم. برای مثال برای 3 جسم می توانیم حالت های زیر را تولید کنیم.
000
001
010
011
100
101
110
111
در این تابع قصد داریم هر کدام از این رشته ها را دریافت کردیم بتوانیم رشته بعدی آن را تولید کنیم و زمانی که به انتها رسیدیدم در این مثال به 111 رسیدیم اعلام کنیم که دیگر تمام شده است و مجدد رشته ها به 000 بر می گردد.
در ورودی تابع ما یک مجموعه از کارکتر‌ها خواهیم داشت که یکی از مثال های فوق هستند و دیگری سایز ارایه ما. در اینجا فرض کنیم ارایه ورودی ما [0,0,0] است و سایز ما نیز 3 است.
کد برنامه را به زبان جاوا خواهیم دید به چه صورت خواهد بود.
public static boolean findNextSubset(char bitString[], int size) {
int n = size - 1;
char c = '1';
int i = 1;
while ((n >= 0) && (c == '1')) {
i = Character.getNumericValue(c);
bitString[n] += i;
if (bitString[n] == '2') {
bitString[n--] = '0';
c = '1';
} else {
c = '0';
n--;
}
}
return (c == '1') ? true : false;
}
امیدوارم مطلب فوق برای شما مفید بوده باشد.
