У меня проблема с программой, которая похожа на рюкзак, но имеет две небольшие отличия.
Первое значение предметов может быть отрицательным.
Второе, если в рюкзаке есть место для предмета Это ДОЛЖНО, даже если оно понижает текущую стоимость упаковки.
Обычный подход не помогает, потому что, если мои вещи
Weigh Value
1 100
2 1
1 -1000
И рюкзак имеет емкость 2, и каждый предмет может go в рюкзак один раз
Первый элемент будет вставлен
0 to backpack of 0
100 to backpack of 1
100 to backpack of 2
Пока все хорошо, но второй элемент никогда не будет go, так как его стоимость ниже, чем первый и третий все разрушает потому что рюкзак 1 будет таким же, но этот ужасный предмет помещается в рюкзак 2, а его стоимость снижается до -900, так как я не могу пропустить его, когда у меня все будет в порядке со вторым предметом и будет иметь значение 1.
Смысл в том, чтобы вставлять предметы, которые кажутся хуже, но занимают больше места, чтобы худшие предметы не могли go дюйма
К сожалению, если предметы были следующие:
Weigh Value
1 100
2 1
1 -10
тогда рюкзак с первым и третьим предметом лучше, чем рюкзак со вторым, поэтому я не могу бездумно наполнить свой рюкзак какими-либо положительными ценностями, чтобы отрицать отрицательные, потому что это иногда (пример выше) не ответ.
I ' м вне идей.