Решить задачу о рюкзаке с общим весом не более 15. Номер предмета 1 2 3

Решить задачу о рюкзаке с общим весом не более 15. Номер предмета 1 2 3 4 5 6 Вес предмета 4 3 2 1 7 4 Цена предмета 4 10 6 6 8 4

Каждый из шести предметов в задаче в одном экземпляре, каждый из них мы либо кладем в рюкзак, либо нет, значит, всего существует 26=64 способа загрузки рюкзака.
Задачу можно решить методом простого перебора.
Составим таблицу перебора, в которой 0 означает, что не кладем предмет, 1 – кладем предмет. Посчитаем вес и если он не превышает 15, находим ценность.
Предмет 1 2 3 4 5 6 Вес
рюкзака Ценность рюкзака
Вес 4 3 2 1 7 4
Ценность 4 10 6 6 8 4
0 0 0 0 0 0 0 0
0 0 0 0 0 1 4 4
0 0 0 0 1 0 7 8
0 0 0 0 1 1 7+4=11 8+4=12
0 0 0 1 0 0 1 6
0 0 0 1 0 1 1+4=5 6+4=10
0 0 0 1 1 0 1+7=8 6+8=14
0 0 0 1 1 1 1+7+4=12 6+8+4=18
0 0 1 0 0 0 2 6
0 0 1 0 0 1 2+4=6 6+4=10
0 0 1 0 1 0 2+7=9 6+8=14
0 0 1 0 1 1 2+7+4=13 6+8+4=18
0 0 1 1 0 0 2+1=3 6+6=12
0 0 1 1 0 1 2+1+4=9 6+6+4=16
0 0 1 1 1 0 2+1+7=10 6+6+8=20
0 0 1 1 1 1 2+1+7+4=14 6+6+8+4=24
0 1 0 0 0 0 3 10
0 1 0 0 0 1 3+4=7 10+4=14
0 1 0 0 1 0 3+7=10 10+8=18
0 1 0 0 1 1 3+7+4=14 10+8+4=1=22
0 1 0 1 0 0 3+1=4 10+6=16
0 1 0 1 0 1 3+1+4=8 10+6+4=1=20
0 1 0 1 1 0 3+1+7=11 10+6+8=1=24
0 1 0 1 1 1 3+1+7+4=15 10+6+8+4=1=28
0 1 1 0 0 0 3+2=5 10+6=16
0 1 1 0 0 1 3+2+4=9 10+6+4=1=20
0 1 1 0 1 0 3+2+7=12 10+6+8=1=24
0 1 1 0 1 1 3+2+7+4=16>15 –
0 1 1 1 0 0 3+2+1=6 10+6+6=1=22
0 1 1 1 0 1 3+2+1+4=12 10+6+6+4=1=26
0 1 1 1 1 0 3+2+1+7=13 10+6+6+8=2=30
0 1 1 1 1 1 3+2+1+7+4=17>15 –
1 0 0 0 0 0 4 4
1 0 0 0 0 1 4+4=8 4+4=8
1 0 0 0 1 0 4+7=11 4+8=12
1 0 0 0 1 1 4+7+4=15 4+8+4=12=16
1 0 0 1 0 0 4+1=5 4+6=10
1 0 0 1 0 1 4+1+4=9 4+6+4==14
1 0 0 1 1 0 4+1+7=15 4+6+8=18
1 0 0 1 1 1 4+1+7+4=16>15 –
1 0 1 0 0 0 4+2=6 4+6=10
1 0 1 0 0 1 4+2+4=10 4+6+4=14
1 0 1 0 1 0 4+2+7=13 4+6+8=18
1 0 1 0 1 1 4+2+7+4=17>15 –
1 0 1 1 0 0 4+2+1=7 4+6+6=16
1 0 1 1 0 1 4+2+1+4=13 4+6+6+4=20
1 0 1 1 1 0 4+2+1+7=14 4+6+6+8=24
1 0 1 1 1 1 4+2+1+7+4=18>15 –
1 1 0 0 0 0 4+3=7 4+10=14
1 1 0 0 0 1 4+3+4=11 4+10+4=18
1 1 0 0 1 0 4+3+7=14 4+10+8=22
1 1 0 0 1 1 4+3+7+4=18>15 –
1 1 0 1 0 0 4+3+1=8 4+10+6=20
1 1 0 1 0 1 4+3+1+4=12 4+10+6+4=1=24
1 1 0 1 1 0 4+3+1+7=15 4+10+6+8=1=28
1 1 0 1 1 1 4+3+1+7+4=19>15 –
1 1 1 0 0 0 4+3+2=9 4+10+6=20
1 1 1 0 0 1 4+3+2+4=13 4+10+6+4=1=24
1 1 1 0 1 0 4+3+2+7=16>15 –
1 1 1 0 1 1 4+3+2+7+4=20>15 –
1 1 1 1 0 0 4+3+2+1=10 4+10+6+6=1=26
1 1 1 1 0 1 4+3+2+1+4=16>15 –
1 1 1 1 1 0 4+3+2+1+7=17>15 –
1 1 1 1 1 1 4+3+2+1+7+4=21>15 –
Найдем такое сочетание предметов, чтобы их ценность была максимальной.
Наибольшая ценность получилась в 31 строке.
Результат: кладем предметы 2, 3, 4, 5