predmeti vo kutii

Mi treba pomosh so zadacava, pozelno bi mi bilo nekoj da mi ja reshi i da mi dade objasnuvanje

Dadeni se M kutii, site so ista golemina (golemina G) i N predmeti. Napishi programa koja ke kaze dali moze site predmeti da se smestat vo kutiite. Eden predmet ne moze da se podeli vo dve kutii.

Ex:
input:
8 4 15 // N, M, G (1<=N,M,G<=20)
7 8 6 9 5 10 4 11 // N-te predmeti

output:
1 // 1 ako moze da se smestat predmetite u kutiite, 0 ako ne moze da se smestat

input:
4 2 15
16 1 1 1

output:
0

p.s ne mi treba brute force reshenie, i greedy ne pominuva

p.p.s. ova ne e oficijalna zadaca, jas ja napraviv(ako vekje postoi vakov problem stavete link od Wikipedia

). Mi treba reshenieto na zadacava za da mozam da go iskoristam kako alatka vo edna zadaca od USACO(zadacata "Raucous Rockers", 3.4.4)

Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.

This message was edited 1 time. Last update was at 13/04/2012 11:12:50

obi1kenobi wrote:Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.

Se soglasuvam so Obi

Greedy raboti

Duri mislam deka imase vakva zadaca na treningot na mendo

obi1kenobi wrote:Зошто не поминува greedy? Или не сфаќам што прашуваш, или нема никаков проблем со greedy-то.

**ne go opishav inputot dobro, vo prviot red se dadeni 3 integers N(brojot na predmeti), M(brojot na kutii) i G(volumenot na site kutii posebno), a vo vtoriot red se dadeni N integers, broevi koi gi opishuvaat volumenite na predmetite.

jas mislam na vakvo greedy: gi sortirash predmetite po rastecki redosled, i polnish edna kutija se dodeka sobira(prvo go stavsh prviot element, pa vtoriot, pa tretiot se dodeka moze kutijata da sobere). koga ke go nadminesh kapacitetot na prvata kutija, probuvash da ja napolnish vtorata kutija itn. Ova go povtoruvash se dodeka ima mesto vo kutiite za sledniot predmet, ili go povtoruvash se dodeka ima predmeti za stavanje. Na kraj, ako si gi iskoristil site elementi pecatish 1(moze elementite da se smestat vo kutiite), vo sprotivno pecatish 0.

ova reshenie ne e tocno, kontra primer e
N: 8 // dadeni se 8 predmeti
M: 4 // dadeni se 4 kutii
G: 15 // prvata kutija ima volumen 15, vtorata 15, tretata 15 i cetvrtata kutija ima volumen 15.
N-te predmeti: 7 8 6 9 5 10 4 11 // predmetite se so vloumen: 7, 8, 6, 9, 5, 10, 11;

greedyto vaka ke raboti:
ja sortira nizata: 4 5 6 7 8 9 10 11
i gi stava predmetite:
vo prvata kutija ke gi stavi predmetite so V = 4 5 6
vo vtorata kutija ke gi stavi predmetite so V = 7 8
vo tretata kutija ke gi stavi predmetie so V=9 (samo eden predmet, bidejki sledniot e so V=10 i nema da go sobere vo preostanatiot prostor)
vo cetvrtata kutija ke go stavi predmetite so V=10
ke ostane predmetot so V=11, odnosno programa ke vrati 0 bidejki ne usteala da gi smesti site predmeti vo kutiite

tocniot rezultat e 1
vo prvata kutija da vlezat predmetite so V=7 8
vo vtorata kutija da vlezat predmetite so V=6 9
vo tretata kutija da vlezat predmetite so V=5 10
vo cetvrtata kutija da vlezat predmetite so V=4 11
bidejki site predmeti se iskoristeni tocnoto reshenie e 1(predmetite mozat da se smestat vo kutiite)

А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..

This message was edited 1 time. Last update was at 13/04/2012 16:03:30

Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

bedzo wrote:А пробај со вакво динамичко. Гледаш во која кутија можеш најмногу предмети да ставиш, па ги вадиш предметите што си ги искористил и продолжуваш за сите кутии, ако ти останале елементи испечати 0, ако не испечати 1. Ова е knapsack проблем како што гледам..

ne te razbiram so sakash da pravish, a inache site kutii imaat ist kapacitet.

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

go razmisliv ova reshenie, ama nema da mi pomogne deka DFS-to ke treba da go povtoruvam 2^N pati (najlosh slucaj N=20,slozenosta O((2^20)*DFS))

This message was edited 1 time. Last update was at 13/04/2012 18:38:26

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

Зошто да не работи? M^2*(М/2)*N сложеност. Поточно ќе го разделиш на М ранец-проблеми и ќе гледаш колку можеш повеќе предмети да ставиш во еден ранец, и потоа ранецот со најмногу ставени предмети ќе го тргнеш (бидејќи ништо неможе да се става во него веќе) и ќе ги извадиш предметите што си ги ставил во ранецот кој ти е најмногу пополнет.

This message was edited 1 time. Last update was at 13/04/2012 18:36:22

Еве го средив ова, мислам дека е точно, а изгледа може и уште да се упрости.
N^2*G

#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
struct rr
{
    int a;
    vector<int> used;
};
bool cc(bool a[],int n)
{
    for(int i=1;i<=n;i++) if(!a[i]) return false;
    return true;
}
int main()
{
    bool vis[22];
    int niz[22],n,m,g,i,j,k;
    cin>>n>>m>>g;
    rr dp[22][5000];
    for(i=1;i<=n;i++) vis[i]=false,cin>>niz[i];
    for(int gg=0;gg<m;gg++)
    {
        if(cc(vis,n))
        {
            cout<<"1"<<endl;
            return 0;
        }
        rr z;
        z.a=0;
        for(j=0;j<=g;j++) dp[0][j]=z;
        for(i=1;i<=n;i++)
        {
            if(vis[i])
            {
                for(j=0;j<=g;j++) dp[i][j]=dp[i-1][j];
            }
            else
            {
                for(j=0;j<=g;j++)
                {
                    if(j-niz[i]>=0)
                    {
                        if(dp[i-1][j-niz[i]].a+niz[i]>dp[i][j].a)
                        {
                            dp[i][j]=dp[i-1][j];
                            dp[i][j].a+=niz[i];
                            dp[i][j].used.push_back(i);
                        }
                    }
                    else dp[i][j]=dp[i-1][j];
                }
                for(int k=0;k<dp[n][g].used.size();k++)
                    vis[dp[n][g].used[k]]=true;
            }
        }
    }
    cout<<"0"<<endl;
    return 0;
}

bedzo wrote:

obi1kenobi wrote:Ова е integer multi-knapsack проблем и по дефиниција нема никакво друго решение освен брутфорс. Користи дфс и ќе биде во ред.

EDIT: Дури сега видов дека сите кутии се со иста големина. Со тоа ограничување, постои динамичко решение.

Зошто да не работи? M^2*(М/2)*N сложеност. Поточно ќе го разделиш на М ранец-проблеми и ќе гледаш колку можеш повеќе предмети да ставиш во еден ранец, и потоа ранецот со најмногу ставени предмети ќе го тргнеш (бидејќи ништо неможе да се става во него веќе) и ќе ги извадиш предметите што си ги ставил во ранецот кој ти е најмногу пополнет.

Кои предмети ќе ги ставиш во кој ранец? Како знаеш дека баш тие предмети што си ги ставил прават оптимално решение? Ај дај напиши (псеудо)код да ти дадам контра-пример.

Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.

bedzo wrote:Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.

greedy со динамичко, тоа треба во signature да си го ставиш, ако не и во алманах да ти го напишат

Ај вака. Имаш кутии што берат 6, 4 и 2, и имаш предмети што тежат 4, 3, 3, 2. Како со твоето динамичко ќе гарантираш дека 3 и 3 ќе завршат во кутијата со големина 6, а не 4 и 2? Ќе ги провериш двата случаи? Ако ги проверуваш двата случаи, тогаш сложеноста на решението е експоненцијална затоа што истава конфигурација ќе ја повторам n пати и ќе мораш сите пермутации да ги испробаш, а ако не ги проверуваш тогаш ова е контра-пример.

Ништо, лоша ми била идеата :Р

obi1kenobi wrote:

bedzo wrote:Razmisluvav na toa pa mi izleze deka mojata idea e greedy so dinamicko, eve kako ke odi:

Gi pominuvame site kutii i za sekoja kutija go pustame dinamickoto sto go postirav pogore, pa kje ja najdeme kutijata koja sme ja ispolnile najmnogu i gi briseme predmetite sto sme gi stavile, ja briseme kutijata i prodolzuvame istoto so ostanatite kutii.

greedy со динамичко, тоа треба во signature да си го ставиш, ако не и во алманах да ти го напишат

Ај вака. Имаш кутии што берат 6, 4 и 2, и имаш предмети што тежат 4, 3, 3, 2. Како со твоето динамичко ќе гарантираш дека 3 и 3 ќе завршат во кутијата со големина 6, а не 4 и 2? Ќе ги провериш двата случаи? Ако ги проверуваш двата случаи, тогаш сложеноста на решението е експоненцијална затоа што истава конфигурација ќе ја повторам n пати и ќе мораш сите пермутации да ги испробаш, а ако не ги проверуваш тогаш ова е контра-пример.

Mi se chini deka Kompirot spomna deka site kutii se so ista golemina

^ Разгледувавме во различни кутии сега. А инаку за со исти кутии го оставив кодот погоре.