Задача о рюкзаке

Из заданного набора вещей надо выбрать, что положить в рюкзак, так чтобы суммарная цена была максимальна и вес не превысил заданной величины.

наименование	часы	картина	радио	ваза	книга	компьютер
цена	175	90	20	50	10	200
вес	10	9	4	2	1	20

Создадим список объектов

function buildItems()
{
	const names = ['часы', 'картина', 'радио', 'ваза', 'книга', 'компьютер']
	const values = [175, 90, 20, 50, 10, 200]
	const weights = [10, 9, 4, 2, 1, 20]
	const items = []
	for (let i = 0; i < values.length; i++)
	{
		items.push({
			name:names[i], 
			value: values[i], 
			weight: weights[i]
		})
	} 
	return items
}
const items = buildItems()

Подмножество вещей мы будем обозначать массивом из 0, 1. 1 если мы берём вешь и ноль, если не берём. Создадим генератор таких последовательностей.

function* genBin(n)//на каждоме шаке получеам 
//увеличенное на 1 двоичное чилсо
{
	let b = []
	for(let i = 0; i < n; i++)
		b.push(0)
	yield b
	let i = n - 1
	while(true)
	{
		if(i == -1)
		{
			return
		}
		else if( b[i] == 1)
		{
			b[i] = 0
			i -= 1
		}
		else
		{
			b[i] = 1
			i = n - 1
			yield b
		}
	}
}
for(let x of genBin(6))//проверим как он рабтает
	console.log(x)

Используя этот генератор, создадим следующий, который будет генерировать всевозможные подмножества из данного множества

function* genPowerSet(items)
{
	for(let x of genBin(items.length))
	{
		let taken = []
		for (let i = 0; i < x.length; i++)
		{
			if (x[i] == 1) taken.push(items[i])
		}
		yield taken
	}
}

Создадим фильтр генерирующий только подходящие по весу наборы

function weightTest(taken, maxWeight)
{
	totalWeight = 0
	for(let t of taken)
	{
		totalWeight += t.weight 
		if(totalWeight > maxWeight)
		{
			return false
		}
	}
	return true
}



function* weightFilter(maxWeight, genSet)
{
	for(let taken of genSet)
	{
		if (weightTest(taken, maxWeight))
			yield taken
	}
	return
}

//Проверим
let setF = weightFilter(20, genPowerSet(items))
for(let taken of setF) console.log(taken) 

Выбреме набор имещий максимальную цену

function genSolution(xFGen)
{
	let totalValue = 0
	let taken = []
	for (let x of xFGen)
	{
		if (value(x) > totalValue)
		{
			totalValue = value(x)
			taken = x.slice()
		}
	}
	return {totalValue: totalValue, taken: taken}
}

function value(taken)
{
	let totalValue = 0
	for(let item of taken)
	{
		totalValue += item.value 
	}
	return totalValue
}
//Проверим
let  sol = genSolution(setF)
console.log(sol.taken)
console.log(sol.totalValue)

Жадный алгоритм

Приближённый метод решения, мы сортируем вещи в наборе по убыванию, по какому-то свойству, например по цене. И затем выбираем те из них, которые подходят по весу.

function greedy(items, maxWeight, cmpFunction)
{
	items.sort(cmpFunction)
	items.reverse()
	let totalWeight = 0
	let totalValue = 0
	const taken = []
	for (let i = 0; i < items.length; i++)
	{
		if( totalWeight + items[i].weight <= maxWeight)
		{
			taken.push(items[i].name)
			totalWeight += items[i].weight
			totalValue += items[i].value
		}
	}
	return {totalValue: totalValue, taken: taken}
}

Приведём примеры функций сортировки по цене и обратному весу.

function cmpValue(itemA, itemB)
{
	let r = itemA.value - itemB.value
	return r
}

function cmpWeightInverse(itemA, itemB)
{
	let r = 1/itemA.weight - 1/itemB.weight
	return r
}

Создадим функцию, которая будет выводить результат

function testGreedy(items, maxWeight, cmpFunction)
{
	const {totalValue, taken} = greedy(items, maxWeight, cmpFunction)
	console.log("Полная цена = ", totalValue)
	console.log("Взяли:", taken)
}

Проверим как все работает

console.log("Сортировка по цене даёт:")
testGreedy(items, 20, cmpValue)
console.log("Сортировка по обратному весу даёт:")
testGreedy(items, 20, cmpWeightInverse)

Решение для сортировки по удельной цене (цена/вес) найдите самостоятельно.