• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
347 wizyt
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!

 
 

 

 

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 (56,900 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 (56,900 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ź

0 głosów
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;
}

 

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

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

2 7
2 3
3 4

Pisze 9 zamiast 10

Podobne pytania

0 głosów
1 odpowiedź 434 wizyt
0 głosów
1 odpowiedź 96 wizyt
0 głosów
1 odpowiedź 363 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...