4. Knapsack-Problem (Rucksack-Problem)

Knapsack-Problem (Rucksack-Problem)

  • D

    mein lösungsansatz funktioniert schon hab nur ein prob

    int N=5;
item items[5];
int maxKnown[100];
String itemKnown[100];

int sack (int cap)
	{int i, space, max, maxi=0, t;
	 if (maxKnown[cap] != -1) return maxKnown[cap];
	 for (i = 0, max = 0; i < N; i++)
		if ((space = cap - items[i].size) >= 0)
			if ((t = sack(space) + items[i].val) > max)
				{max = t; maxi=i;}
maxKnown[cap] = max; itemKnown[cap] = itemKnown[cap] + items[maxi].name;

//items[i].count=items[i].count+1;
return max;

    N anzahl wie viele Sachen es gibt die in den rucksack können also es gibt 5 unterschiedliche
    cap größe des sacks
    items ist meine klasse mit den sachen die es gibt
    maxKnown[] speicher für den besten ermittelten wert
    itemKnown[] in das array soll reingespeichert werden welche items im sack sind

    meine item klasse

    class item
{public:	String name;
	int size;
	int val;
};

    meine objekte

    items[0].name="Würstchen";
items[0].size=3;
items[0].val=4;
items[1].name="Wodka";
items[1].size=4;
items[1].val=5;
items[2].name="Fanta";
items[2].size=7;
items[2].val=10;
items[3].name="Pringles";
items[3].size=8;
items[3].val=11;
items[4].name="Pinjata";
items[4].size=9;
items[4].val=13;

    jetzt will ich wie oben gesagt in itemKnown immer die items speichern, die für die bestelösung, im sack sind

    ich möchte für einen sack der 12 größ die besten lösung haben das sieht man auch so 1 pinjata und 1 würstchen das gibt dan einen wert von 17. das bekomme ich auch heraus. blos wenn ich mir as array angucke kommt dann folgendes raus:
    würstchen
    würstchen
    würstchen
    würstchen
    wodka
    wodka
    würstchen

    pringles
    pinjata

    würstchen

    so die letzten 2 wären die richtige lösung sind aber die abstände dazwichen und gleih an pinjata pringles dran. kann mir da einer helfen das mit variabler größe das ich immer die richtigen items angezeigt bekomme und nicht immer alles bei denen er durchgegangen ist?

    0
  • W

    Die Ausgabe ist nach dem Value im Sack geordnet. D.h. in der 17. Zeile sollte das Würstchen erscheinen und in der 12. die Pinjata. Es wird für jeden max. Sack-Wert (val) nur das erste (!) item gespeichert.
    Wenn Du als Ergebnis alle die Dinge haben möchtest, die in den Sack mit dem maximalen Wert passen, so musst Du den Inhalt im Return-Code mit zurückgeben, statt es global abzulegen. Das kann man z.B. in einer Liste von item's machen. Hier eine Alternative:

    #include <list>
#include <numeric>      // accumulate
#include <string>       // string

struct AddVal
{
    int operator()( int sum, const item& it )
    {
        return sum + it.val;
    }
};
std::list< item > sack2( int cap )
{
    int max_val = 0;
    std::list< item > maxi;
    for( item* i = items; i != items + sizeof(items)/sizeof(*items); ++i )
    {
        int space = cap - i->size;
        if( space >= 0 )    // item '*i' passt in den Sack
        {
            std::list< item > t = sack2( space ); // liefert die item's mit max. Sack-Wert mit Sack-Größe 'space'
            const int t_val = std::accumulate( t.begin(), t.end(), i->val, AddVal() );
            if( t_val > max_val )   // Sack hat größeres 'val' als max
            {
                max_val = t_val;
                t.push_front( *i ); // 1.Item noch hinzufügen
                maxi = t;
            }
        }
    }
    return maxi;
}

    Die Liste, die von sack2( 12 ) erzeugt wird, enthält dann nur das Würstchen und die Pinjata.

    Gruß
    Werner

    0
  • D

    erst mal danke hab aber wegen folgendem prob keine ahnung

    Kann man dawas machen kann den wert nicht in nem edit feld ausgeben
    [C++ Error] Unit1.cpp(91): E2034 Cannot convert 'std::list<item,std::allocator<item> >' to 'AnsiString'

    0
  • H

    Der Richter schrieb:

    Kann man dawas machen kann den wert nicht in nem edit feld ausgeben
    [C++ Error] Unit1.cpp(91): E2034 Cannot convert 'std::list<item,std::allocator<item> >' to 'AnsiString'

    Das passt besser ins VCL-Forum.

    0
  • C

    Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum VCL/CLX (Borland C++ Builder) verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • B

    Hallo,

    Häng einfach c_str() an dein Listenelement an, dann klappts auch mit dem AnsiString.

    0
  • D

    Braunstein schrieb:

    Hallo,

    Häng einfach c_str() an dein Listenelement an, dann klappts auch mit dem AnsiString.

    sorry versteh ich nicht

    0
  • A

    Hallo

    string Test = "A";
Edit->Text = Test.c_str();

    bis bald
    akari

    0
  • D

    akari schrieb:

    Hallo

    string Test = "A";
Edit->Text = Test.c_str();

    bis bald
    akari

    ok soviel versteh ich jetzt. hab jetzt mehre variationen ausprobiert aber brings nicht hin. wie lautet der code genau anhand des beispiels oben?

    0
  • B

    Das ist hier doch etwas anderes. Du hast die Strings ja schon im richtigen Format, willst also nur darauf zugreifen;
    Was willst du übrigens wohin speichern. In den obigen Quelltexten kommt kein Editfeld vor.
    Hast du jetzt eine list<Item>?
    Hier mal der Code zum Schreiben des ersten Eintrages in der list in ein Editfeld.

    std::list< item > Items;
// jetzt die list anhand des Algorithmusses füllen
std::list< item >::iterator it = Items.begin();
Edit->Text = it->name;

    oder mal zum Schreiben aller itemnamen in eine StringList

    TStringList *list = new TStringList;
// Schleife durchläuft die Liste und fügt alle Einträge einer StringList zu
for(std::list< item >::iterator it = Items.begin(); it!=Items.end(); ++it)
   liste->Add(it->name);
// irgendwas mit der StringList machen
delete list; //löschen nicht vergessen
    0
  • D

    ja de funktion sack2 hat ja am ende nen return maxi das würde ich gerne in nem edit feld ausgeben

    0
Anmelden zum Antworten