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

Question

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!

 

 

 

 

Comments

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

---

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

---

ooooooo ostatni problem to chyba nasz?

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

Idziaszek opisał w 10 linijkach chyba

---

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

---

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

Answer 1

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;
}

 

Comments

To zadanie jest podejrzane, kod dostaje 100pkt, ale np. dla testu 

2 7
2 3
3 4

Pisze 9 zamiast 10