Текущ брой на Списание ИнфоМан
 


Есенен турнир 2004, Задача B3. СУМА

Уловието на задачата може да прочетете тук.

Решение

Задачата е леко модифициран вариант на следната много известна задача: ако е дадено множество от монети с целочислени стойности, да се определят всички суми, които могат да се получат като използваме някои (евентуално всички)от дадените монети. Решението на тази задача се базира на метода на динамичното оптимиране. Накратко, ако с t[i] бележим стойността на i-тата монета, дефинираме функция F(k,s) по следния начин

F(k,s) = 1 <=>можем да получим сума s, използвайки само монетите с индекси 1...k.

Тогава:

F(k,s) = 1,

  1. ако F(k-1,s) =1, т.е. ако сме могли да получим сумата s с монетите 1...k-1
  2. ако F(k-1,s-t[k])=1, т.е. ако можем да получим такава сума, към която ако прибавим стойността на k-тата монета ще получим сума s.

Така F(n,x) ще ни даде отговор на въпроса “може ли с всичките n монети да получим сумата x, т.е. като получим всички стойности на F от вида F(n,x) ще разберем кои суми можем да получим и кои не.

Сложността напресмятането на таблица със стойностите на F(k,s) за всяко kи s очевидно е O(N*S), където N е броят на монетите, а S е максималната сума, за която ще искаме отговор.

За да сведем задачата до тази така познта задача трябва да се справим само с едно нещо. Стойностите на монетите са цели числа, а на касовите бележки от входа десетични дроби. В условието изрично е казано, че стойностите на дробите не надвишават 99.99 и нямат повече от две цифри след десетичната запетая. Тогава е достатъчно всяка десетична дроб да бъде умножена по 100. По този начин със сигурност ще получим цели числа в интервала [1;10000]. Умножаваме и M по 100. След това решаваме добре известната задача, формулирана по-горе. Така вече знаем всички суми по-малки или равни на M (умножено предварително по 100), които могат да се получат, използвайки дадените ни касови бележки. Тогава при всяко получаване на нова сума ще проверяваме каква е разликата между нея, и най-малкото цяло числоL (ако има такова), което е по-голямо или равно на нея и също така е по-малко или равно на M Ако тази разлика е по-малка от текущия минимум, или пък е равна на текущия минимум, но числото L е по-голямо от най-голямото намерено за момента, тогава променяме текущия минимум да бъде тази разлика и едновременно с това сме намерили нова най-голяма стойност за L. След като минем през всички такива суми, отговорът ни е най-голямата стойност за L, намерена до момента.

Тъй като разликите с предходната задача са само умножаването по 100 и една проверка за текущ минимум, сложността на решението става O(N*(M*100)).

Примерна реализация:

#include <stdio.h>
#include <math.h>

#define MAXN 101
#define MAXM 1000001

char p[MAXN][MAXM]; // masiw za dinami4noto
// po princip e dostaty4no da pazim samo poslednite dwa reda, no
// w slu4aia ne e nujno zaradi ogranicheniata na zadachata

int t[MAXN]; // chislata ot whoda, umnojeni po 100

int main () {
int i,j,N,M,L,min=2000000000,sum=-1;
double value;
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++) {
		scanf("%lf",&value);
		t[i] = (int)ceil(100*value); // umnojawame po 100 
		// chislata. polzwame ceil, a ne prosto 
		// t[i] = (int)100*value , poneje poniakoga chislata 
		// wmesto naprimer 2.7 se chetat kato 2.6999999 i 
		// togawa (int)(100*value) shte dowede do 269, koeto
		// pri niakoi whodni danni moje da dowede do greshen otgowor
	}

	p[0][0] = 1; // suma 0 winagi mojem da polu4im

	for (j=1;j<=N;j++) {
		L = 100; // 1wata gorna granica - 1 lev 

		p[j][0] = 1;
		for (i=1;i<=M*100;i++) {
		
			// ako sme mojeli da polu4im dosega, pak mojem 
			p[j][i] = p[j-1][i]; 
			
			// dali mojem da polu4im nowata suma?
			if (i>=t[j] && p[j-1][i-t[j]]) 
				p[j][i] = 1;

			if (p[j][i]) { // nov optimum?
				if (L-i<min || ((L-i==min) && (sum<L))) {
					min = L-i;
					sum = L;
				}
			}
			if (i%100==0) // nowo cialo chislo za gorna granica
				L+=100;
		}
	}
	printf("%d\n",sum/100);
	return 0;
}

Автор: Слави Маринов


обратно към брой 27