Function knapsack_01 

pub fn knapsack_01(weights: &[usize], values: &[i64], capacity: usize) -> i64

0/1 xalta masalasi — buyumni yo butun olamiz, yo umuman olmaymiz.

Holat: dp[w] = sig’imi w bo’lgan xaltaga joylash mumkin bo’lgan maksimal qiymat.

O’tish: har bir buyum uchun dp[w] = max(dp[w], dp[w - og'irlik] + qiymat).

Muhim nozik nuqta: sig’im bo’yicha teskari (kattadan kichikka) yuramiz — aks holda bitta buyumni bir necha marta olib qo’yamiz (u holda bu boshqa masala: “cheksiz xalta”).

• Time: O(n·W), Space: O(W) — 2D jadvalni 1D ga siqdik.

Bu pseudo-polinomial murakkablik: W kirish hajmi emas, kirish qiymati. W juda katta bo’lsa (masalan, 10⁹) bu usul ishlamaydi.

Misol

use rust_algorithms::dp::knapsack_01;

let ogirliklar = [1, 3, 4, 5];
let qiymatlar = [1, 4, 5, 7];
assert_eq!(knapsack_01(&ogirliklar, &qiymatlar, 7), 9); // 3 + 4 → 4 + 5

// Ochko'zlik bu yerda xato qiladi: eng "zich" buyum (5/4=1.25) ni olsa 7+1=8 chiqadi