Bagaimanakah Kami Boleh Mengenalpasti Barangan yang Termasuk dalam Penyelesaian Knapsack Optimum?

Menentukan Item dalam Penyelesaian Knapsack Optimum

Memandangkan algoritma Knapsack, yang membungkus item secara optimum untuk memaksimumkan jumlah nilai, artikel ini menangani tambahan cabaran untuk mengenal pasti item khusus yang termasuk dalam penyelesaian optimum.

Untuk bermula, kami menyelidiki Pelaksanaan algoritma Knapsack:

int Knapsack::knapsack(std::vector<Item>& items, int W) {...}

Untuk mendapatkan semula item yang terlibat dalam penyelesaian optimum, kami boleh memanfaatkan maklumat yang disimpan dalam matriks yang dikira:

std::vector<vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));

Kod Pseudo:

line = W
i = n
while (i > 0):
  if dp[line][i] - dp[line - weight(i)][i-1] == value(i):
    // Item 'i' is in the knapsack
    i--
    line -= weight(i)
  else: 
    i--

Proses lelaran ini berulang melalui matriks. Apabila perbezaan berat sepadan dengan saiz item, item itu dianggap sebagai sebahagian daripada penyelesaian optimum. Item tersebut dikecualikan daripada pertimbangan dan proses diteruskan.

Dengan menggunakan teknik ini, kami boleh menentukan item mana yang membentuk gabungan paling berharga dalam beg beg tanpa memerlukan storan data tambahan. Pendekatan ini bukan sahaja cekap tetapi juga memberikan pandangan berharga tentang komposisi penyelesaian optimum.

Atas ialah kandungan terperinci Bagaimanakah Kami Boleh Mengenalpasti Barangan yang Termasuk dalam Penyelesaian Knapsack Optimum?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!