Knapsack 1

Knapsack 1

Atcoder medium

لديك مجموعة تحتوي على \(N\) عنصرًا، كل عنصر \(i\) له وزن \(w_i\) وقيمة \(v_i\). اختر مجموعة جزئية من العناصر بحيث لا يتجاوز وزنها الإجمالي \(W\). حدد أكبر قيمة إجمالية ممكنة.

Solution

سنحل هذه المشكلة باستخدام البرمجة الديناميكية.

دعنا نعرف الحالة:

\(f(i, capacity)\) هي أكبر قيمة إجمالية ممكنة بالنظر فقط إلى العناصر من \(0\) حتى \(i\) بأقصى وزن إجمالي ممكن. \(capacity\)

بعد ذلك، نعرف الانتقال. في كل خطوة، يمكننا إما إضافة العنصر \(i\) أو إستبعاده.

في حالة إضافة العنصر \(i\)، يكون الانتقال:

\(f(i, capacity) = f(i - 1, capacity - w_i) + v_i\)

في حالة إستبعاده، يكون الانتقال:

\(f(i, capacity) = f(i - 1, capacity)\)

نظرًا لأننا لا نستطيع تحديد أي الخيارين أفضل مسبقًا، فإننا نأخذ القيمة الأكبر بين الانتقالين:

\(f(i, capacity) = max(f(i - 1, capacity ), f(i - 1, capacity - w_i) + v_i)\)

في هذه المشكلة، تكون الحالة الأساسية:

\(f(0,\text{capacity}) = \begin{cases} v_i, & \text{capacity} \ge w_i,\\[6pt] 0, & \text{capacity} < w_i. \end{cases}\)

تعقيد المساحة في الخوارزمية يحدده عدد الحالات، وهو \(O(N \cdot W)\).

التعقيد الزمني هو عدد الحالات N W مضروبًا في تعقيد كل انتقال \(O(1)\)، لذا يكون التعقيد الكلي \(O(N \cdot W)\).

#include <iostream>
using namespace std;

long long dp[200][200000];
int v[200], w[200]; 


long long f (int i, int capacity) {

    if (i == 0) {
    if (capacity < w[i]) {
      return 0;
    }
    else {
      return v[i];
    }
    }

  if (dp[i][capacity] != -1) {
    return dp[i][capacity];
  }

  // i في حالة إستبعاد العنصر 
  dp[i][capacity] = f(i - 1, capacity);

  // i في حالة أخذ العنصر 
  if (capacity >= w[i]) {
    dp[i][capacity] = max(dp[i][capacity], f(i - 1, capacity - w[i]) + v[i]);
  }

  return dp[i][capacity];
}


int main() {
  
    for (int i = 0; i < 200; i++) {
    for (int j = 0; j < 200000; j++) {
          dp[i][j] = -1;
    }
    }

    int n, weight;
    cin >> n >> weight;
  
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i];
  }

  cout << f(n - 1, weight) << endl;
}