نسبت مجموع زیرمجموعه‌ها

http://www.lamsade.dauphine.fr/~bazgan/Papers/icalp98.pdf

می‌خواهیم دو زیرمجموعه مجزا از اشیا انتخاب کنیم که نسبت مجموع آنها مینیمم شود.

قسمتی از این مسأله که تکراری است و نیاز به حساب کردن همه‌ی حالت‌ها ندارد، این است که همه‌ی زیرمجموعه‌های مجموعه اصلی را که حساب کنیم شامل هر دو مجموعه هست. پس کافی است حالتی را پیدا کنیم که اختلاف آنها مینیمم شود. سپس به ازای هر سود چک می‌کنیم که دو زیرمجموعه مجزا هستند که آن سود را بدهند یا نه. چک کردن این کار با توجه به اینکه زیرمجموعه‌ها را با آرایه‌های دودویی نشان داده‌ایم ساده است.