Zadanie Problem Plecakowy Letni obóz treningowy po 15 OIJ, przed EJOI 2021

pytanie zadane 27 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z takim zadaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/ple/

Mam dwie obserwacje z tym zadaniem:

1 - Zapewne wejdzie tu jakieś dp, tylko nie wiem jakie

2 - Jeśli są dwa przedmioty, i jeden z nich więcej waży, i ma mniej lub tyle samo smakołyków, to można go odrazu usunąć z rozważań, nie wiem czy to coś da, ale może się przydać.

Z góry dziękuję za pomoc!

Pokaż 24 poprzednich komentarzy

komentarz 30 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

pomieszało mi się to chyba, tam jest opisane chyba ten nasz sposób.

komentarz 30 marca 2023 przez Whistleroosh Maniak (57,400 p.)

Kojarze że widziałem kiedyś rozwiązanie do tego problemu, ale wersji gdzie przedmioty nie mają wartości i to korzystało z modulo. Natomiast nasz pomysł powinien chyba działać jeśli ta tablica dp będzie wystarczająco duża, tylko nie wiem jak bardzo

komentarz 2 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

ooooooo ostatni problem to chyba nasz?

http://www.algonotes.com/en/knapsacks/

Idziaszek opisał w 10 linijkach chyba

komentarz 2 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

tylko nie wiem czy to się da jakoś przełożyć.

komentarz 2 kwietnia 2023 przez Whistleroosh Maniak (57,400 p.)

To jest to o czym pisałem wyżej. Wzorcówka pewnie wygląda podobnie, ale trzeba odpowiednio dobrać rozmiar tablicy dp, bo <= 500 jest raczej za mała

1 odpowiedź

odpowiedź 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

UWAGA UWAGA UWAGA!

Jest 100pkt, rozwiązanie jest dokładnie takie samo, jak myślałeś. Iterujemy się po kandydatach, dopychamy jeden najbardziej jak się da, a resztę dopychamy plecakiem. Kod:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

struct Przedmiot
{
    ll masa;
    int waga;
};

int n = 0;
ll m = 0, sum = 0, wyn = 0;
vector<Przedmiot> przedmioty;
vector<ll> dp;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    przedmioty.assign(n,{});
    for (int i = 0; i < n; ++i)
        cin >> przedmioty[i].waga >> przedmioty[i].masa;

    for (int i = 0; i < n; ++i)
        sum += przedmioty[i].waga;

    dp.assign(sum+1,0);

    for (int i = 0; i < n; ++i)
        for (int j = przedmioty[i].waga; j <= sum; ++j)
            dp[j] = max(dp[j], dp[j-przedmioty[i].waga] + przedmioty[i].masa);

    for (int i = 0; i < n; ++i)
        wyn = max(wyn,(m / przedmioty[i].waga) * przedmioty[i].masa + dp[m % przedmioty[i].waga]);

    cout << wyn << '\n';

    return 0;
}