ранец алгоритм с двумя весами

Question

У меня есть вопросы, заключается в следующем:

Решите задачу о рюкзаке 0-1 (не дробная) Предполагая, что каждый объект имеет вес w1 или w2 (там только два весов). Емкость = W, алгоритм должен работать на O (nlogn).

Я попытался решить, жадный алгоритм не работает, алгоритм динамического программирования - O (n * W).

Может ли кто-нибудь дать мне подсказку. Спасибо.

Answer 1

Вы можете разделить элементы в 2-х частей, одна из которых имеют w1 как вес, а другие, которые имеют w2, как вес.

Теперь вы можете отсортировать два списка выше в соответствии с их расходами.

A1: отсортированы по цене в порядке убывания, элементы, которые имеют вес, как w1

A2: отсортированные по цене в порядке убывания, элементы, которые имеют вес, как w2

Теперь вы можете создать префиксная сумма обоих массивов позволяет называть их P1, P2.

пример:

Array : 11, 8, 5, 3, 1

Prefix sum : 11, 19, 24, 27, 28

После того как вы сумму префикса, вы можете перебрать P1 массива и попытаться включить элементы UPTO индекс-го. После того, как мы включим элементы до i, у нас есть W - (w1*i) вес слева, мы можем попытаться выполнить двоичный поиск этого веса в массиве P2.

псевдокод:

A : input array 
create A1 : cost of elements having w1 weight 
create A2 : cost of elements having w2 weight 

sort(A1, descending) 
sort(A2, descending) 

for(i=0;i <= A1.size();i++){ 
     P1[i] = P[i-1] + A1[i]; 
     P2[i] = P[i-1] + A2[i]; 
} 
int ans = 0; 
for(i=1;i<=A1.size();i++){ 
     if(i * w1 <= W){ 
      int wLeft = W - i * w1; 
      int ans = binarySearch(wLeft, P2) + p1[i]; 
     } 
} 
ans => contains the answer 

//-----------Binary search function 
int binarySearch(int weight, P2[]){ 
     int start = 0, end = P2.size(), ans = 0; 
     int mid = (start+end)/2; 
     while(start <= end){ 
      if(mid * w2 <= weight){ 
        start = mid + 1; 
        ans = max(ans, p2[mid]); 
      }else{ 
        end = mid - 1; 
      } 
     } 
return ans 
} 

Общая сложность O(n * log n).

Как было предложено @j_random_hacker, мы можем выполнять итерацию по второму префиксному массиву, поскольку мы можем только улучшить решение путем добавления элементов, это упростит код, удалив двоичный поиск.

Answer 2

Поскольку есть два веса вы можете:

Первое использование как многие элементы w1, как у вас есть или может поместиться в W. После них, как многие w2, насколько это возможно.

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

Максимальный вес рюкзака от всех итераций будет вам anwser и алгоритм будет работать в O (N)