Yangom

Yangom

صورت مساله

میخواهیم با استفاده از D حرف N کلمه بسازیم به طوری که هیچ کدام از کلمات پیشوند یکدیگر نباشند و همچنین هزینه درست کردن آن مینیمم باشد. هزینه کل برابر مجموع هزینه هر کلمه است و هزینه هر کلمه برابر مجموع هزینه های حروف آنهاست.

توضیح و بررسی

من خودم وقتی این سوال را خوندم یاد مساله کد هافمن افتادم ولی کد هافمن حالت خاصی از این مساله میشه ولی رسیدن به این نقطه برای شروع خوبه،اول سعی میکنیم که از راه حل کد هافمن استفاده کنیم و با یک مقدار تغییر مساله را حل کنیم بعد از چند دقیقه به احتمال زیاد به این نتیجه میرسیم که اگه هزینه حروف را بصورت صعودی مرتب کنیم اتفاق خوبی میافته ولی بعد میبینیم این مساله Greedy حل نمیشه بعد تا اینجا بازم به یک نقطه بهتری میرسیم بعد یک کم دیگه هم فکر میکنیم میبینیم راه حلش Binary Search،Backtrack یا Network flow نیست بعدبه سادگی نتیجه میگیریم که Dynamic Programming میتونه باشه، الان به جایی رسیدیم که میتونم کم کم مساله را بازش کنیم.

چند تا مثال که روی کاغذ حل کنیم به این نتیجه میرسیم که حرف اول هر کلمه ( first )، تعداد کلماتی که باید بسازیم () و اندیسی که کاراکتر بعدی میخواهد اضافه شود ( depth ) میتونن اجزای تشکیل دهنده حالات ما در راه حل Dynamic باشن. بعد سعی میکنیم که یک تابع بنویسیم که مساله را حل کنه.

int solve ( int first, int n, int depth );

که این تابع به ما میگه کمترین هزینه برای تولید کلمه که با first شروع میشن و تا به حال depth کاراکتر از این کلمات درست شدن چه قدر میشه. خوب سه حالت بوجود میاد:

1. اصلا از first استفاده نکنیم.

2. یک کلمه را با first تموم کنیم و n-1 تای بقیه را با استفاده از کاراکترهای بعدی بسازیم.

3. تعدادی از کلمات با first ادامه پیدا کنن و بقیه با کاراکترهای دیگه ادامه پیدا کنن.

بعد به دنبال یک سری شرط خروج میگردیم:

1. اگر n مساوی صفر شد جواب صفر میشه.

2. اگر depth >= N شد یعنی کلمهای میخواهیم درست کنیم که طول آن بیش از تعداد کل کلماتی است که نیاز داریم پس واضح است که نباید ادامه دهیم.

3. اگه first>=D نیز نباید ادامه دهیم.

خوب این لحظه زندگیمون شیرین میشه و شاد و خندون البته تیز وار شروع میکنیم کد این تابع را مینویسیم:

#include <iostream>
#include <algorithm>
#include <memory>
 
using namespace std;
 
const int inf = 1000000000;
const int max_n = 201 ;
 
int dp [max_n][max_n][max_n] ;
int cost [max_n] ;
int N, D;
 
int solve ( int first , int n , int depth ){
	if ( n == 0 ) 
		return 0 ;
	if ( first == D ) 
		return inf ;
	if ( depth >= N ) 
		return inf ;
 
	int & ret = dp [first][n][depth];
	if ( ret != -1 )
		return ret;
 
	ret = solve ( first + 1 , n , depth ) ;
 
	int temp = cost [first] + solve ( first + 1 , n - 1 , depth ) ;
	ret = min ( ret , temp );
 
	for ( int i=2 ; i<=n ; i++ ){
		int temp = cost [first]*i + solve ( 0 , i , depth + 1 ) + 
                       solve ( first + 1 , n - i , depth );
		ret = min ( ret , temp ) ;
	}
	return ret;
}
 
int main (){
	while ( cin >> N >> D ){
		if ( N == 0 && D == 0 ) 
			break ;
 
		for ( int i=0 ; i<D ; i++ )
			cin >> cost [i] ;
 
		sort ( cost , cost + D ) ;
		memset ( dp , -1 , sizeof dp ) ;
		cout << solve ( 0 , N , 0 ) << endl;
	}
}

بعد Submit میکنیم و خیلی مطمئن میریم یک سوال دیگه رو حل کنیم و لذت میبریم از راه حلمون، بعد از جند دقیقه که جواب Submit اومد احتمالا با Time Limit Exceeded مواجه خواهیم شد.

حالا به دنبال علت میگردیم و مبینیم که O(n^3) خونه حافظه داریم که برای هر کدومشون O(n) بار کار انجام میدهیم و الگوریتم ما O(n^4) است و برای N=200 حتما Time out میشود.

نتیجه اخلاقی 1: همیشه قبل از این که چیزی را کد کنیم پیچیدگی زمانی آن را حساب کنیم..

حالا سعی میکنیم راه حلمون را سریعتر کنیم، کمی به آرگومنهای توابع نگاه میکنیم:

solve ( first + 1 , n , depth ) ; // 1
solve ( first + 1 , n - 1 , depth ) ;//2
solve ( 0 , i , depth + 1 ) ;//3
solve ( first + 1 , n - i , depth ) ;//4

اگر حروف را بر حسب هزینه مرتب کنیم، فراخوانی اول کاملا بی مورد است چون حداقل یک کلمه را با first باید بسازیم.

با کمی دقت متوجه میشویم که depth فقط در فراخوانی سوم یکی زیاد میشود و ما از depth فقط به خاطر جلوگیری از افتادن توی فراخوانی تکراری و در نتیجه Stack OverFlow و همچنین جلوگیری از طولانی شدن بیش از حد کلمات از آن استفاده میکنیم، پس اگر راهی پیدا کنیم که depth را حذف کنیم و توی loop هم نیافتیم مساله حل میشود.

یک کم دیگه دقت میکنیم میبینیم(فراخوانی اول را حذف کرده ایم) که first همواره زیاد میشود و همواره کم میشود، فقط در یک حالت ممکن است در loop بیافتیم که آن هم وقتیست که first = 0 و n = i باشد که آنهم با یک شرط درست میکنیم حالا راه حل ما O(n^3) میشود و مساله حل میشود.

کد برای حل این مساله

کد جدید هم در زیر آمده است:

#include <iostream>
#include <algorithm>
#include <memory>
using namespace std;
 
const int max_n = 201 ;
int dp [max_n][max_n];
int cost [max_n] ;
int alpha_count , word_count ;
const int inf = 1000000000 ;
int f ( int first , int n  ){
	if ( n == 0 ) return 0;
	if ( first >= alpha_count ) return inf;
 
	int & ret = dp [first][n];
	if ( ret != -1 ) return ret;
 
	ret = inf;
 
	int temp = cost [first] + f ( first + 1 , n - 1 ) ;
	ret = min ( ret , temp ) ;
 
	for ( int i=2 ; i<=n ; i++ ){
		if ( i == n  && first == 0 ) continue ;
		temp = cost [first]*i + f (0 , i) + f (first+1 , n - i) ;
		ret = min ( ret , temp ) ;
	}
 
	return ret;
}
int main (){
	while ( cin >> word_count >> alpha_count ){
		if ( word_count + alpha_count == 0 ) break;
 
		for ( int i=0; i<alpha_count ; i++ )
			cin >> cost [i] ;
 
		sort ( cost , cost + alpha_count ) ;
		memset ( dp , -1 , sizeof dp );
		cout << f ( 0 , word_count) << endl;
	}
}
// Author: Mr.Arsalan