'pack-problem' eindimensional

kartoffelsack

Habe eine (große) zahl und viele (kleine) Zahlen und muss herausbekommen, ob es möglich ist die große Zahl als Summe der kleinen Zahlen zu bilden.

Das ganze erinnert mich ein bisschen an ein Koffer-Pack-Problem, nur dass meine einzelteile eindimensional sind und dass ich nicht möglichst viel reinkriegen will sondern ich die 'Menge' und die Einzelteile kenne und überprüfen muss, ob es zusammen passt.

Habt Ihr vielleicht ein paar weiterführende Stichwörter, Links etc. mit denen ich einen Einstieg finde?

Brute-Force alles durchprobieren?

Prof84

kartoffelsack schrieb:

...
Habt Ihr vielleicht ein paar weiterführende Stichwörter, Links etc. mit denen ich einen Einstieg finde?

http://de.wikipedia.org/wiki/Metrik
http://de.wikipedia.org/wiki/Metrischer_Raum

Blue-Tiger

kartoffelsack schrieb:

Habe eine (große) zahl und viele (kleine) Zahlen und muss herausbekommen, ob es möglich ist die große Zahl als Summe der kleinen Zahlen zu bilden.

Das ganze erinnert mich ein bisschen an ein Koffer-Pack-Problem, nur dass meine einzelteile eindimensional sind und dass ich nicht möglichst viel reinkriegen will sondern ich die 'Menge' und die Einzelteile kenne und überprüfen muss, ob es zusammen passt.

Habt Ihr vielleicht ein paar weiterführende Stichwörter, Links etc. mit denen ich einen Einstieg finde?

Spontan wuerd mir einfallen: Zerleg sowohl die grosse als auch die Summe aller kleinen Zahl in Primfaktoren. Wenn du alle Primfaktoren der grossen Zahl in den Primfaktoren der kleinen Zahlen findest, bist fertig. Aber bei wirklich sehr grossen Zahlen ist halt die Primfaktorenzerlegung recht aufwaendig.

@Prof84:
Ich sehe jetzt nicht wirklich, wie die Abstraktion des metrischen Raums bei diesem Problem behilflich sein sollte. Würdest du das netterweise näher ausfühern? (Den Op freut es sicher auch )

Blue-Tiger schrieb:

Spontan wuerd mir einfallen: Zerleg sowohl die grosse als auch die Summe aller kleinen Zahl in Primfaktoren. Wenn du alle Primfaktoren der grossen Zahl in den Primfaktoren der kleinen Zahlen findest, bist fertig. Aber bei wirklich sehr grossen Zahlen ist halt die Primfaktorenzerlegung recht aufwaendig.

wie soll das funktionieren?

große Zahl = 9
kleine Zahlen = {5,4,1}

Primfaktoren der großen Zahl: 3,3
Primfaktoren der Summe aller kleinen Zahlen: 2,5

Hmmm. Liegt wohl daran, dass Primfaktoren bei Produkten wesentlich mehr helfen, als bei Summen, oder ?

@Kartoffelsack:

Hallo

das ist das "subset sum"-Problem, ein NP-vollständiges Problem, ein
Spezialfall des allgemeineren "Knapsack Problems".

Wikipedia hat einige Artikel zu dem Thema.

Grüße

Blue-Tiger

C-x C-c schrieb:

Blue-Tiger schrieb:

Spontan wuerd mir einfallen: Zerleg sowohl die grosse als auch die Summe aller kleinen Zahl in Primfaktoren. Wenn du alle Primfaktoren der grossen Zahl in den Primfaktoren der kleinen Zahlen findest, bist fertig. Aber bei wirklich sehr grossen Zahlen ist halt die Primfaktorenzerlegung recht aufwaendig.

wie soll das funktionieren?
große Zahl = 9
kleine Zahlen = {5,4,1}

Primfaktoren der großen Zahl: 3,3
Primfaktoren der Summe aller kleinen Zahlen: 2,5
Hmmm. Liegt wohl daran, dass Primfaktoren bei Produkten wesentlich mehr helfen, als bei Summen, oder ?

stimmt, mein Fehler

life

Kannst ja das Problem rekursiv definieren. Seien die Zahlen also von 1-n durchnummeriert mit Wert z_i > 0 (1 <= i <= n) und g > 0 die Zielsumme, dann gilt:
Zerlegung(n,g) ist möglich wenn Zerlegung(n,g-z_n) (bzw. Zerlegung(n-1,g-z_n) wenn man jede Zahl nur einmal benutzen darf) oder Zerlegung(n-1,g) möglich ist.
Weiter ist Zerlegung(0,y) = false für y > 0, Zerlegung(x,0) = true und Zerlegung(x,y) = false für y < 0.

Laufzeit sollte O(n * g) sein, wenn das alles int sind ~~

Kartoffelsack is dumm und riecht nach kack'

kartoffelsack

mist, Jimbo Cojones kennt mich

Jester

life schrieb:

Kannst ja das Problem rekursiv definieren. Seien die Zahlen also von 1-n durchnummeriert mit Wert z_i > 0 (1 <= i <= n) und g > 0 die Zielsumme, dann gilt:
Zerlegung(n,g) ist möglich wenn Zerlegung(n,g-z_n) (bzw. Zerlegung(n-1,g-z_n) wenn man jede Zahl nur einmal benutzen darf) oder Zerlegung(n-1,g) möglich ist.
Weiter ist Zerlegung(0,y) = false für y > 0, Zerlegung(x,0) = true und Zerlegung(x,y) = false für y < 0.

Laufzeit sollte O(n * g) sein, wenn das alles int sind ~~

Aha, und wie funktioniert das, wenn es mit z_n nicht geht, aber wenn man die rausläßt geht's? Das deckt Dein Verfahren garnicht ab.

Gemerell wäre es schon merkwürdig, wenn es so einen einfachen Polynomial-Zeit-Algorithmus für ein NP-vollständiges Problem gäbe.

life

Ob das Problem wirklich NP-schwer ist nach den Vorausetzungen die ich formuliert habe, ist auch fraglich.
Im allgemeinen gibt es auch keinen Vergleichsbasierten Algorithmus, der dir schneller als O(n log n) ein Array sortiert. Wenn ich aber z.B. festlege, dass jedes Element des Arrays eine Ganzzahl im Wertebereich 1..n ist, kann ich dir direkt einen Sortieralgorithmus mit linearer Laufzeit angeben

Der Algorithmus, den ich angegeben habe, hat auch Laufzeit O(n*g) (und funktioniert nur unter den angegebenen Einschränkungen) und ist somit nur dann linear, wenn man g als vorher bekannte Konstante ansieht.

Nochmal zur Rekursionsformel: Die unterscheidet genau 2 Fälle: Entweder man nimmt die n-te Zahl oder man nimmt sie eben nicht. Damit sind offensichtlich alle Fälle abgedeckt ~~

edit: dein einwand versteh ich nicht. Wenn es mit n-1 Zahlen möglich ist das Problem zu lösen, ist es auch mit einer zusätzlichen Zahl zu lösen, indem man die zusätzliche Zahl einfach nicht in die Summe nimmt..

Jester

life schrieb:

Ob das Problem wirklich NP-schwer ist nach den Vorausetzungen die ich formuliert habe, ist auch fraglich.
Im allgemeinen gibt es auch [b]keinen Vergleichsbasierten[b] Algorithmus, der dir schneller als O(n log n) ein Array sortiert. Wenn ich aber z.B. festlege, dass jedes Element des Arrays eine Ganzzahl im Wertebereich 1..n ist, kann ich dir direkt einen Sortieralgorithmus mit linearer Laufzeit angeben

Genau, vergleichsbasiert geht's nicht schneller. Nie, auch unter den tollsten Voraussetzungen nicht.

Der Algorithmus, den ich angegeben habe, hat auch Laufzeit O(n*g) (und funktioniert nur unter den angegebenen Einschränkungen) und ist somit nur dann linear, wenn man g als vorher bekannte Konstante ansieht.

Nochmal zur Rekursionsformel: Die unterscheidet genau 2 Fälle: Entweder man nimmt die n-te Zahl oder man nimmt sie eben nicht. Damit sind offensichtlich alle Fälle abgedeckt ~~

Ja, zwei Fälle, man nimmt sie, oder man tut's nicht. Diese Entscheidung muß man für jede Zahl einmal treffen, das macht insgesamt 2^n Möglichkeiten, die man durchprobieren muß. Ich sehe nicht, wie Du da auf Linearzeit kommst.

life

Indem ich die rekursionsformel bottom-up auflöse. Schau dir mal Stichwort dynmanische Programmierung an. Vielleicht schreib ich später noch was dazu, hab grad keine Zeit

HumeSikkins

Hallo,
wenn die kleinen Zahlen alle >= 0 sind würde ich diese Zahlen vorher noch sortieren. Das hilft dabei den Baum zu beschneiden.

Ein Backtrack-Algo könnte dann in etwa so aussehen:

bool testPossible2(std::vector<int>& num, int sum) {
	if (num.empty()) return sum == 0;
	std::sort(num.begin(), num.end(), greater<int>());
	std::vector<size_t> nStack;
	size_t n = 1;
	nStack.push_back(n);
	const size_t end = num.size();
	int curSum = num[0];
	bool sumReachedOnce = false;
	while (curSum != sum && n != end) {
		bool sumReached = false;
		while (curSum < sum && n != end) {
			curSum += num[n];
			nStack.push_back(++n);
		}
		if (curSum != sum) {
			sumReached |= curSum > sum;
			sumReachedOnce |= sumReached;
			curSum -= num[n-1];
			nStack.pop_back();
			if (n == end && !nStack.empty()) {
				n = nStack.back();
				nStack.pop_back();
				curSum -= num[n-1];
			}
			if (!sumReached && !nStack.empty()) {
				n = sumReachedOnce ? nStack.front() : end;
				nStack.clear();
				curSum = 0;
			}
			if (nStack.empty()) {
				sumReachedOnce = false;
			}
		}
	}
	return curSum == sum;
}

Wie man das Problem in linearer Zeit lösen kann, ist mir allerdings nicht klar.

life

#include <iostream> 
#include <vector>
#include "windows.h"

using namespace std; 

bool zerlegung(const vector<unsigned int>& zahlen, const unsigned int g) {
	bool** mem = new bool*[zahlen.size()+1];
	for(unsigned int i = 0; i < zahlen.size()+1; i++)
		mem[i] = new bool[g+1];

	for(unsigned int i = 0; i < zahlen.size()+1; i++)
		mem[i][0] = true;

	for(unsigned int i = 1; i < g+1; i++)
		mem[0][i] = false;

	for(unsigned int i = 1; i < zahlen.size()+1; i++) {
		for(unsigned int j = 1; j < g+1; j++) {
			if(j < zahlen[i-1]) {
				mem[i][j] = mem[i-1][j];
			}
			else {
				mem[i][j] = mem[i-1][j] || mem[i-1][j-zahlen[i-1]];
			}
		}
	}

	bool returnv = mem[zahlen.size()][g];

	for(unsigned int i = 0; i < zahlen.size()+1; i++)
		delete[] mem[i];
	delete[] mem;

	return returnv;
}

int main() 
{ 
	vector<unsigned int> zahlen;
	zahlen.push_back(3);
	zahlen.push_back(14);
	zahlen.push_back(5);
	zahlen.push_back(1);
	zahlen.push_back(43);
	zahlen.push_back(12);
	zahlen.push_back(17);
	//zahlen.push_back(18);

	unsigned int g = 50;

	cout << zerlegung(zahlen, g) << endl;

	system("pause");
    return 0; 
}

so gehts im Prinzip :>
Laufzeit: O(ng)
Speicher: O(ng)

HumeSikkins

Hübsch, allerdings wäre es imo eigenartig, wenn man g als Konstante vernachlässigen würde. Wenn die einzelnen Zahlen positiv sind, dann muss g ja immer mindestens so groß wie n sein. Alles andere ist uninteressant.

life

HumeSikkins schrieb:

Hübsch, allerdings wäre es imo eigenartig, wenn man g als Konstante vernachlässigen würde. Wenn die einzelnen Zahlen positiv sind, dann muss g ja immer mindestens so groß wie n sein. Alles andere ist uninteressant.

Man muss ja nicht jede Zahl nehmen, also ist es auch bei g < n nicht uninteressant ;).
Trotzdem würde ich auch nicht g einfach als Konstante auffassen (habs ja auch immer mit angegeben)...