Messages posted by: bedzo

^ А што ќе ти е тешко ако кликнеш 2 клика повеќе?

Ова да не ти е вишок? 38ми ред.
readln;

@ob1kenobi

А да почнуваме прво да ги полниме најмалите кутии? Така ќе бидеме сигурни за овој контра-тест пример.

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

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

http://www.cs.org.mk/index.php/natprevari/srednoob...egionalennatprevar/2-razno/122

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.

Еве го средив ова, мислам дека е точно, а изгледа може и уште да се упрости.
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;
}

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

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

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

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

Го поедноставив кодот и ја решив. Климент ако ти треба некоја помош кажи.

Ау епа по се изгледа треба 2 пати да пуштам динамичко. Еднач само за множење и еднач само за одзимање. Така множењето ќе има предност.

11*11+111+1+1+1+1+1+1+1+1+1

Ova vrakja pomalku od 36

Еве како ти го средив за во стринг да ти го стави.

filip_bujaroski wrote:

bedzo wrote:8 од интернационални е исто така многу лесна.

Aj daj mi hint nekoj za dinamickoto na taa?
Stvarno ne mi teknuva nishto od pocetok

низа dp[n][2]

dp[i][0] ти означува ако го земеш и-тиот правоаголник вертикално
dp[i][1] ти означува ако го земеш хоризонтално

и ќе ги пополнуваш по тоа што ќе земеш некое од предходниот ред, за да го максимизираш резултатот со i правоаголници.