Vinnaren i pepparkakshustävlingen!
2017-03-09, 17:16
  #1
Medlem
derivats avatar
Har lite siffror
1718
1710
1891
1766
1741
1711
1763
1762
1795
1928
1802
1747
1758
1781
1911
1773
1761
1747
1729
1765
1725
1734
1717
1895
Summan = 42630
Jag vill lägga dessa i 6 grupper, går det få varje grupp till samma summa 62630/6 = 7105?
Går inte det så vill jag ha grupperna så nära 7105 som möjligt.

Har flyttat runt dessa nummer själv och kommer inte närmare än:
7104, 7107, 7104, 7103, 7107, 7105
Citera
2017-03-09, 18:54
  #2
Medlem
inneskos avatar
Citat:
Ursprungligen postat av derivat
Har lite siffror
1718
1710
1891
1766
1741
1711
1763
1762
1795
1928
1802
1747
1758
1781
1911
1773
1761
1747
1729
1765
1725
1734
1717
1895
Summan = 42630
Jag vill lägga dessa i 6 grupper, går det få varje grupp till samma summa 62630/6 = 7105?
Går inte det så vill jag ha grupperna så nära 7105 som möjligt.

Har flyttat runt dessa nummer själv och kommer inte närmare än:
7104, 7107, 7104, 7103, 7107, 7105


Bästa lösningen jag finner är

Grupp 1: 1718, 1747, 1911, 1729
Grupp 2: 1710, 1891, 1758, 1747
Grupp 3: 1766, 1763, 1795, 1781
Grupp 4: 1741, 1711, 1928, 1725
Grupp 5: 1762, 1802, 1773, 1765
Grupp 6: 1761, 1734, 1717, 1895

Totala avvikelsen från 7105 är 6 med denna lösning, för din lösning är den 8 så jag antar att denna skulle vara bättre.
Citera
2017-03-09, 18:58
  #3
Medlem
nihilverums avatar
Citat:
Ursprungligen postat av derivat
Har lite siffror
1718
1710
1891
1766
1741
1711
1763
1762
1795
1928
1802
1747
1758
1781
1911
1773
1761
1747
1729
1765
1725
1734
1717
1895
Summan = 42630
Jag vill lägga dessa i 6 grupper, går det få varje grupp till samma summa 62630/6 = 7105?
Går inte det så vill jag ha grupperna så nära 7105 som möjligt.

Har flyttat runt dessa nummer själv och kommer inte närmare än:
7104, 7107, 7104, 7103, 7107, 7105

Den här artikeln beskriver den uppgift du tänker på. Den dåliga nyheten är att problemet är NP-komplett redan för fallet att dela upp i två delgrupper, vilket betyder att det inte finns någon effektiv generell lösning. Artikeln beskriver dock en pseudo-polynomiell algoritm för att hantera fall där det totala antalet siffror inte är så stort. Ditt exempel här ovan är dock redan ganska stort, så det kan nog gå ganska segt att försöka köra ett program som löser uppgiften.
Citera
2017-03-09, 19:17
  #4
Medlem
inneskos avatar
Citat:
Ursprungligen postat av nihilverum
Den här artikeln beskriver den uppgift du tänker på. Den dåliga nyheten är att problemet är NP-komplett redan för fallet att dela upp i två delgrupper, vilket betyder att det inte finns någon effektiv generell lösning. Artikeln beskriver dock en pseudo-polynomiell algoritm för att hantera fall där det totala antalet siffror inte är så stort. Ditt exempel här ovan är dock redan ganska stort, så det kan nog gå ganska segt att försöka köra ett program som löser uppgiften.

Kan ju avslöja att jag skrev ett program för att finna den lösning jag gjorde, om det inte är någon bugg i koden jag skrev så är den lösning jag skrev optimal.
Citera
2017-03-09, 21:09
  #5
Medlem
derivats avatar
Citat:
Ursprungligen postat av innesko
Bästa lösningen jag finner är

Grupp 1: 1718, 1747, 1911, 1729
Grupp 2: 1710, 1891, 1758, 1747
Grupp 3: 1766, 1763, 1795, 1781
Grupp 4: 1741, 1711, 1928, 1725
Grupp 5: 1762, 1802, 1773, 1765
Grupp 6: 1761, 1734, 1717, 1895

Totala avvikelsen från 7105 är 6 med denna lösning, för din lösning är den 8 så jag antar att denna skulle vara bättre.

Coolt, tackar.

Anade att det fanns någon typ av algoritm, men utöver mina mattekunskaper.

Fipplar även med programmering lite, försökte tänka ut någon typ av lösning men även här är mina kunskaper för svaga. Hade varit skoj att se koden som du skrev
Citera
2017-03-09, 21:34
  #6
Medlem
inneskos avatar
Citat:
Ursprungligen postat av derivat
Coolt, tackar.

Anade att det fanns någon typ av algoritm, men utöver mina mattekunskaper.

Fipplar även med programmering lite, försökte tänka ut någon typ av lösning men även här är mina kunskaper för svaga. Hade varit skoj att se koden som du skrev

Testade att skriva det i javascript vilket jag inte skriver i så ofta och saker är inte direkt optimalt, men det fungerar iaf.

Algoritmen är väl egentligen ganska enkel, det handlar bara om att gå igenom alla möjliga sätt att sätta ihop 6 grupper på och se vilken som ger minsta felet. Detta blir ju dock alldeles för många olika sätt så man får pruna sökrummet ganska hårt, vilket inte är allt för svårt.

Kod:
function getSubset(set, order) {
	let subset = [];
	let antiSubset = [];
	let index = 0;
	while (order > 0) {
		if ((order & 1) === 1) {
			subset.push(set[index]);
		} else {
			antiSubset.push(set[index]);
		}
		index++;
		order = Math.floor(order/2);
	}
	
	for (; index < set.length; index++) {
		antiSubset.push(set[index]);
	}
	return {subset: subset, antiSubset: antiSubset};
}

function sumArray(array) {
	return array.reduce((a, b) => a + b, 0);
}

function logSolution(result) {
	console.log("Error: " + result.bestError);
	for (let i = 1; i <= 6; i++) {
		console.log(result.solution[i]);
	}
}

function selectGroup(numbersLeft, grpNumber, targetSum, currentError, result) {
	if (grpNumber === 6) {
		let newError = currentError + Math.abs(sumArray(numbersLeft) - targetSum);
		if (newError < result.bestError) {
			result.bestError = newError;
			result.solution[grpNumber] = numbersLeft;
			logSolution(result);
		}
	} else {
		for (let i = 1; i < (1 << numbersLeft.length); i+=2) {
			let subsets = getSubset(numbersLeft, i);
			let newError = currentError + Math.abs(sumArray(subsets.subset) - targetSum);
			if (newError < result.bestError) {
				result.solution[grpNumber] = subsets.subset;
				selectGroup(subsets.antiSubset, grpNumber + 1, targetSum, newError, result);
			}
		}
	}
}

let numbers = [1718, 1710, 1891, 1766, 1741, 1711, 1763, 1762, 1795, 1928, 1802,
1747, 1758, 1781, 1911, 1773, 1761, 1747, 1729, 1765, 1725, 1734, 1717, 1895];
selectGroup(numbers, 1, sumArray(numbers)/6, 0, {bestError: 8, solution: new Array()});
Citera
2017-03-09, 23:12
  #7
Medlem
fermions avatar
Vill bara påpeka att detta varken rör sig om "siffror" eller "nummer" utan om tal
Siffror är 0,1,2,...9 och kan användas för att uttrycka tal. Tal heter "number" på engelska - vilket kanske förklarar användandet av "nummer".
Citera
2017-03-09, 23:28
  #8
Medlem
derivats avatar
Citat:
Ursprungligen postat av fermion
Vill bara påpeka att jag tycker detta varken rör sig om "siffror" eller "nummer" utan om vad jag kallar tal
Siffror anser jag är 0,1,2,...9, och dessa använder jag för att uttrycka tal. Tal kallar jag "number" på engelska - vilket kanske förklarar användandet av "nummer".

Citera

Stöd Flashback

Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!

Stöd Flashback