Szczegółowe omówienie zadania Knapsack 1:
Link do powyższego omówienia zadania Knapsack 1: https://youtu.be/rN7NFTpGMiI?t=989
Omówienie kodu zadania Knapsack 1: https://youtu.be/rN7NFTpGMiI?t=4426
Link do treści zadania Knapsack 1 i możliwości umieszczania rozwiązań: https://atcoder.jp/contests/dp/tasks/dp_d
Zadanie Knapsack 1 pokazuje rozwiązanie problemu plecakowego: https://youtu.be/rN7NFTpGMiI?t=1575
Jaki jest wzór na n-tą komórkę problemu plecakowego: https://youtu.be/rN7NFTpGMiI?t=3336
Złożoność problemu plecakowego: https://youtu.be/rN7NFTpGMiI?t=3336
Problem plecakowy z wykorzystaniem pojedynczej tablicy: https://youtu.be/rN7NFTpGMiI?t=3596
Czy problem plecakowy można rozwiązać zachłannie? https://youtu.be/rN7NFTpGMiI?t=1292
Gdzie ma zastosowania problem plecakowy? https://youtu.be/rN7NFTpGMiI?t=32
Jakie są minusy problemu plecakowego? https://youtu.be/rN7NFTpGMiI?t=5139
Kody dynamików są krótkie, ładne i przyjemne! https://youtu.be/rN7NFTpGMiI?t=4426
–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625
Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php
Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109
–
Kod C++ programu "Knapsack 1", który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAXW = 1e5 + 7;
long long dp[MAXW];
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, W;
cin >> n >> W;
for (int i = 1; i <= n; ++i) {
int w, v;
cin >> w >> v;
for (int j = W; j >= w; --j) {
// mamy dwie opcje: nie bierzemy albo bierzemy rzecz (w, v):
dp[j] = max(dp[j], dp[j - w] + v);
}
}
cout << dp[W] << '\n';
return 0;
}
Kod C++ programu "Knapsack 1", który jest omówiony w powyższym filmie i który otrzymuje 100%
–
Kod Python programu Knapsack 1, który otrzymuje 100%:
def solve(): N, W = map(int, input().split()) dp = [0] * (W + 1) for i in range(N): w, v = map(int, input().split()) for j in range(W, w-1, -1): # mamy dwie opcje: nie bierzemy albo bierzemy rzecz (w, v): dp[j] = max(dp[j], dp[j - w] + v) print(dp[W]) solve()