Meyvə bayramı (Həll təhlili)

$t$ tutumlu bir bel çantası var. Dəyərləri $a$ və $b$ olan iki əşya mövcuddur. Onların hər birini bel çantasına istənilən sayda dəfə qoymaq olar. İki əşya üçün bel çantası məsələsini həll edirik.

Tutaq ki, əgər Bessi $i$-ə bərabər toxluq əldə edə bilirsə, dp[i] = 1 olsun. İndi Bessi su içir. Belə ki, dp[i] = 1 olan hər $i$ qiyməti üçün dp[i / 2] = 1 təyin edirik.

İndi yenidən iki əşya üçün bel çantası məsələsini həll edirik. Bessinin su içdikdən sonra əldə edə biləcəyi toxluqları tapırıq.

Nümunə

Verilmiş nümunəyə baxaq. Portağallar və limonlar üçün bel çantası məsələsini həll edirik.

Bessi su içir.

Yenidən portağallar və limonlar üçün bel çantası məsələsini həll edirik.

Bessinin maksimum toxluğu $8$-ə bərabərdir.

Alqoritmin realizasiyası

$dp$ massivini elan edək, burada Bessi $i$-ə bərabər toxluq əldə edə bilərsə, dp[i] = 1 olur.

#define MAX 5000001
int dp[MAX];

Giriş məlumatlarını oxuyuruq.

scanf("%d %d %d", &t, &a, &b);

Bel çantasını ilkinləşdiririk: heç nə yeməsə, $0$ toxluğuna nail olmaq mümkündür.

dp[0] = 1;

Bel çantasına portağalları qoyuruq.

for (i = a; i <= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;

Bel çantasına limonları qoyuruq.

for (i = b; i <= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Bessi su içir. Əgər $i$ toxluğuna nail olunubsa, onda $i/2$ toxluğuna da nail olmaq mümkündür.

for (i = 1; i <= t; i++)
  if (dp[i] == 1) dp[i / 2] = 1;

Yenidən portağallar və limonlar üçün bel çantası məsələsini həll edirik.

for (i = a; i <= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;
for (i = b; i <= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Bessinin əldə edə biləcəyi maksimum toxluğu tapır və çap edirik.

for (i = t; i > 0; i--)
  if (dp[i] == 1) break;
printf("%d\n", i);

Python realizasiyası

Giriş məlumatlarını oxuyuruq.

t, a, b = map(int, input().split())

$dp$ massivini elan edək, burada Bessi $i$-ə bərabər toxluq əldə edə bilərsə, dp[i] = 1 olur.

dp = [0] * (t + 1)

Bel çantasını ilkinləşdiririk: heç nə yeməsə, $0$ toxluğuna nail olmaq mümkündür.

dp[0] = 1

Bel çantasına portağalları qoyuruq.

for i in range(a, t + 1):
  if dp[i - a] == 1: dp[i] = 1

Bel çantasına limonları qoyuruq.

for i in range(b, t + 1):
  if dp[i - b] == 1:  dp[i] = 1

Bessi su içir. Əgər $i$ toxluğuna nail olunubsa, onda $i/2$ toxluğuna da nail olmaq mümkündür.

for i in range(1, t + 1):
  if dp[i] == 1: dp[i // 2] = 1

Yenidən portağallar və limonlar üçün bel çantası məsələsini həll edirik.

for i in range(a, t + 1):
  if dp[i - a] == 1: dp[i] = 1
for i in range(b, t + 1):
  if dp[i - b] == 1: dp[i] = 1

Bessinin əldə edə biləcəyi maksimum toxluğu tapır və çap edirik.

for i in range(t, 0, -1):
  if dp[i] == 1: break
print(i)