rucksack.go

package main

import "fmt"

type item struct {
	name    string
	gewicht int
	wert    int
}

type rucksack []item

var items []item
var maxGewicht int
var ergebnis rucksack

func (r rucksack) gewicht() int {
	var gewicht int
	for _, v := range r {
		gewicht = gewicht + v.gewicht
	}
	return gewicht
}

func (r rucksack) wert() int {
	var wert int
	for _, v := range r {
		wert = wert + v.wert
	}
	return wert
}

func main() {
	maxGewicht = 30
	items := []item{
		{"Horst", 6, 10},
		{"karl", 2, 7},
		{"Hans", 6, 4},
		{"Otto", 5, 1},
		{"Ernst", 5, 3},
		{"Müller", 5, 4},
		{"Egon", 4, 6},
		{"Harald", 7, 6},
		{"Nils", 4, 5},
		{"Bibi", 1, 3},
		{"Holger", 6, 7},
		{"Abraham", 8, 5},
		{"Gondolf", 3, 2},
		{"Bertram", 5, 9},
		{"Baltasar", 7, 6},
		{"Torben", 3, 5},
		{"Willi", 4, 4},
	}
	var ruck rucksack
	untersuche(ruck, items)

	fmt.Println("Eingangsgrösse:", items)
	fmt.Println("MaxGewicht", maxGewicht)
	fmt.Println("Ergebnis:", ergebnis)
	fmt.Println("Gesamtgewicht:", ergebnis.gewicht())
	fmt.Println("Gesamtwert:", ergebnis.wert())
}

func untersuche(ruck rucksack, rest []item) {
	for i, v := range rest {
		if ruck.gewicht()+v.gewicht <= maxGewicht {
			var neuerRest []item = make([]item, 0, len(rest)-1)
      
      // The next line (not commented out) is working. If I do something of the following the program needs much time, and I don't know why
			// var neuerRucksack rucksack = make([]item, 0, len(ruck)) // not working - because copy() needs the destination to have enough length (not just capacity)
      // var neuerRucksack rucksack = make([]item, len(ruck)+1) // not working - because there will be a new zerovalue inserted. append() will add an item after the zerovalueitem
			// var neuerRucksack rucksack = make([]item, 0, len(ruck)+1) // not working - because copy() needs the destination to have enough length (not just capacity) 
			var neuerRucksack rucksack = make([]item, len(ruck))
      
			neuerRest = append(neuerRest, rest[0:i]...)
			neuerRest = append(neuerRest, rest[i+1:]...)
			copy(neuerRucksack, ruck)
			neuerRucksack = append(neuerRucksack, v)
			if neuerRucksack.wert() > ergebnis.wert() {
				ergebnis = neuerRucksack
			}
			untersuche(neuerRucksack, neuerRest)
		}
	}

}