Aladdinin bel çantası#1661

Aladdinin bel çantası (Həll təhlili)

Tutaq ki, $d p_{k} [s]$ dp_k[s] — yalnız ilk $k$ növ əşyadan istifadə etməyə icazə verildikdə, çəkisi $s$ -dən çox olmayan yükün maksimal dəyəridir.

Çəkisi $i$ olan yükü tərtib edərkən iki mümkün variantı nəzərdən keçirək:

$k$ -cı növ əşyadan istifadə etməmək: bu halda optimal qiymət dəyişməz, yəni

d p_{k} [i] = d p_{k - 1} [i]

dp_k[i] = dp_{k - 1}[i]

$k$ -cı növ əşyadan istifadə etmək: onda onun $w_{k}$ w_k çəkisi bel çantasının tutumunun bir hissəsini tutacaq, dəyər isə $v_{k}$ v_k qədər artacaq, yəni

d p_{k} [i] = d p_{k} [i - w_{k}] + v_{k} .

dp_k[i] = dp_k[i - w_k] + v_k.

Yükün dəyərini maksimuma çatdırmaq tələb olunduğundan, aşağıdakı rekurrent münasibəti alırıq:

d p_{k} [i] = ma x (d p_{k - 1} [i], d p_{k} [i - w_{k}] + v_{k}), w_{k} \leq i \leq s

dp_k[i] = max(dp_{k - 1}[i], dp_k[i - w_k] + v_k), w_k \le i \le s

Əsas hallar:

d p_{0} [i] = 0 v ∋ d p_{k} [0] = 0

dp_0[i] = 0~v\ni~dp_k[0] = 0

Tutaq ki, $f (k, s)$ f(k, s) funksiyası ilk $k$ növ əşyadan istifadə edərək, çəkisi $s$ -dən çox olmayan bel çantasına yığıla bilən yükün maksimal dəyərini hesablayır. Onda aşağıdakı rekurrent münasibət doğrudur:

f (k, s) = ma x (f (k - 1, s), f (k, s - w [k]) + v [k])

f(k, s) = max(f(k - 1, s), f(k, s - w[k]) + v[k])

Qalır ki, $f (k, s)$ f(k, s) funksiyasının qiymətini memoizasiya istifadə edərək hesablayaq.

Alqoritmin realizasiyası

İşçi massivləri elan edək:

$w [i]$ — $i$ -ci növ əşyanın çəkisi;
$p [i]$ — $i$ -ci növ əşyanın dəyəri;
$d p [i]$ — çəkisi $i$ -dən çox olmayan yükün maksimal dəyəri;

#define MAXW 252
#define MAXN 37
int w[MAXN], p[MAXN];
int dp[MAXW];

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", \&s, \&n);
for (i = 0; i \< n; i++)
  scanf("%d %d", \&w[i], \&p[i]);

$n$ növ əşyanı ardıcıl olaraq emal edirik.

for (k = 0; k \< n; k++)
{

$k$ növ əşyalardan istifadə etmə imkanını nəzərə alaraq, $d p$ massivinin qiymətlərini yenidən hesablayırıq. Hər növ əşyanın sayı məhdudlaşdırılmadığından, hər əşya bir neçə dəfə seçilə bilər.

  for (i = w[k]; i \<= s; i++)
    dp[i] = max(dp[i], dp[i - w[k]] + p[k]);
}

Cavabı çap edirik.

printf("%d\n", dp[s]);

Alqoritmin realizasiyası — rekursiya

İşçi massivləri elan edək:

$w [i]$ — $i$ -ci növ əşyanın çəkisi;
$p [i]$ — $i$ -ci növ əşyanın dəyəri;
$d p [i]$ — çəkisi $i$ -dən çox olmayan yükün maksimal dəyəri;

#define MAXW 252
#define MAXN 37
#define INF 2000000000
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

$f (k, s)$ f(k, s) funksiyası ilk $k$ növ əşyadan istifadə edərək, çəkisi $s$ -dən çox olmayan bel çantasına yığıla bilən yükün maksimal dəyərini hesablayır.

int f(int k, int s)
{

Əgər $k = 0$ k = 0 və ya $s = 0$ s = 0 olarsa, bel çantası boşdur və onun dəyəri $0$ -a bərabərdir.

  if (k == 0 || s == 0) return 0;

Əgər $s \< 0$ olarsa, biz icazə verilən çəkini aşmışıq və bu variantın mənası yoxdur. Buna görə $- I N F$ qaytarırıq ( $I N F$ — müəyyən bir böyük ədəddir).

  if (s \< 0) return -INF;

Əgər $f (k, s)$ f(k, s) qiyməti artıq hesablanıbsa, onu qaytarırıq.

  if (dp[k][s] != -1) return dp[k][s];

$f (k, s)$ f(k, s) qiymətini hesablayırıq və onu $d p [k] [s]$ dp[k][s]-də yadda saxlayırıq.

  return dp[k][s] = max(f(k - 1, s), f(k, s - w[k]) + v[k]);
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d", \&s, \&n);
for (i = 1; i \<= n; i++)
  scanf("%d %d", \&w[i], \&v[i]);

Cavabı hesablayır və çap edirik.

memset(dp, -1, sizeof(dp));
printf("%d\n", f(n, s));