Knapsack - thuật toán sức mạnh vũ phu

Question

Tôi đã tìm thấy mã này để giải quyết vấn đề Knapsack sử dụng cơ chế lực lượng vũ phu (điều này chủ yếu là để học tập, vì vậy không cần phải chỉ ra năng động là hiệu quả hơn). Tôi nhận được mã để làm việc, và hiểu được hầu hết nó. PHẦN LỚN. Đây là câu hỏi:

Tôi đã nhận thấy hai điều kiện đó, rằng tôi không biết chúng hoạt động như thế nào và tại sao chúng lại có trong mã - Tôi biết chúng rất quan trọng, vì bất kỳ thay đổi nào tôi đã tạo ra kết quả sai:

// if bit not included then skip 
if (((i >> j) & 1) != 1) continue; 

// if bit match then add 
if (((bestPosition >> j) & 1) == 1) 
{ 
    include.Add(Items[j]); 
} 

Dưới đây là cả lớp, và cách tôi gọi nó ra từ chính:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace KnapSack2 
{ 
    class BruteForce 
    { 
     public double Capacity { get; set; } 
     public Item[] Items { get; set; } 

     public Data Run() 
     { 
      int bestValue = 0; 
      int bestPosition = 0; 
      int size = Items.Length; 

      var permutations = (long)Math.Pow(2,size); 

      for (int i = 0; i<permutations; i++) 
      { 
       int total = 0; 
       int weight = 0; 
       for (int j = 0; j<size; j++) 
       { 
        //jeżeli bit "not included" to omin" 
        if(((i>>j)&1)!=1) 
         continue; 
        total += Items[j].v; 
        weight += Items[j].w; 
       } 
       if (weight <= Capacity && total>bestValue) 
       { 
        bestPosition = i; 
        bestValue = total; 
       } 
      } 
      var include = new List<Item>(); 
      for (int j = 0; j<size; j++) 
      { 
       // jeżeli bit pasuje, wtedy dodaj 
       if (((bestPosition>>j) & 1)==1) 
        include.Add(Items[j]); 
      } 
      return new Data { BestValue = bestValue, Include = include }; 

     }//End of Run 


    } 
} 

Calling ra trong chính

var ks = new BruteForce 
{ 
    Capacity = MaxWeight, 
    Items = items.ToArray() 
}; 

Data result = ks.Run(); 

Lớp Item chỉ là một đối tượng đơn giản giữ giá trị, trọng lượng và ID

Answer 1

& Đây là bitwise-AND

Các Bitwise-VÀ hành so sánh từng bit của toán hạng đầu tiên của mình vào bit tương ứng của nó toán hạng thứ hai. Nếu cả hai bit là 1, chút kết quả tương ứng được thiết lập để 1. Nếu không, tương ứng chút kết quả được thiết lập để 0.

Trong khi >> này là các nhà điều hành phải thay đổi

Các toán tử dịch chuyển phải (>>) dịch chuyển toán hạng nhất của nó ngay bằng số bit được chỉ định bởi toán hạng thứ hai của nó.

Nói như vậy, chúng ta hãy xem biểu thức sau đây

if (((i >> j) & 1) != 1) continue; 

và cố gắng tìm hiểu nó.

Ban đầu, điều này i >> j sẽ dịch chuyển các bit của i bởi j vị trí.

Ví dụ, hãy để chúng tôi có nhiệm vụ sau đây:

int number = 5; 

Các đại diện nhị phân của number là:

0000 0000 0000 0000 0000 0000 0000 0101 

Nếu chúng ta xác định một số nguyên mới như:

int shiftNumbersBitByOne = a >> 1; 

Sau đó, biểu diễn nhị phân của shiftNumbersBitByOne sẽ là:

0000 0000 0000 0000 0000 0000 0000 0010 

Sau đó, kết quả của thao tác này và 1, chúng tôi áp dụng toán tử bitwise AND.

Chính xác nhà điều hành này là gì?

Mặc dù thực tế là định nghĩa rõ ràng, một ví dụ sẽ làm cho nó rõ ràng hơn.

Lết rằng chúng ta có những con số nhị phân a và b, sau đó là kết quả của a&b như sau:

a =  0001 0100 1010 0001 1000 1010 1101 0011 
b =  0010 1100 1111 0111 0011 1010 1011 0111 
a & b = 0000 0100 1010 0001 0000 1010 1001 0011 

Điều đó đang được nói, đi vào hoạt động này (i >> j) & 1 chúng tôi áp dụng Bitwise-VÀ hành giữa kết quả của i >> j và biểu diễn nhị phân của 1

0000 0000 0000 0000 0000 0000 0000 0001 

Khi kết quả của (i >> j) & 1 sẽ là 1?

này sẽ xảy ra khi và chỉ khi chữ số cuối cùng của i >> j là 1.

Cập nhật

Trên chúng ta giải quyết các cách phần - Tôi không có ý tưởng làm thế nào họ làm việc. Bây giờ chúng tôi sẽ giải quyết số lý do tại sao một phần - lý do tại sao họ có mã số.

Hãy xác định vấn đề của chúng tôi, vấn đề về Knapsack. Theo wikipedia

Các bài toán xếp ba lô hay vấn đề ba lô là một vấn đề trong tổ hợp tối ưu hóa: Cho một tập các hạng mục, mỗi một khối lượng và giá trị, xác định số lượng của từng hạng mục để đưa vào một bộ sưu tập rất rằng tổng trọng lượng nhỏ hơn hoặc bằng một giới hạn nhất định và tổng giá trị càng lớn càng tốt.

Theo trên, nó là đơn giản mà

// This is the total weight limit. 
public double Capacity { get; set; } 

và

// This is an array with all the given items. 
public Item[] Items { get; set; } 

Bên cạnh đó, dựa trên mã của bạn, chúng ta có thể suy ra rằng mỗi mục có một giá trị và trọng lượng mà có thể được truy cập tương ứng là item.v và item.w. Tôi đề nghị bạn đổi tên này thành giá trị và trọng lượng tương ứng, để mã của bạn trở nên có ý nghĩa hơn.

Rõ ràng, điều này int size = Items.Length; là số lượng các mặt hàng có sẵn.

Toàn bộ vấn đề về việc tại sao một phần bắt đầu ở đây:

var permutations = (long)Math.Pow(2,size); 

các permutations là gì? permutations đại diện cho điều gì?

Trước khi chúng tôi trả lời câu hỏi này, hãy suy nghĩ về cách chúng tôi có thể đại diện cho mục nào của bộ sưu tập các mục sẽ được sử dụng trong giải pháp cuối cùng. Tôi cho rằng chúng ta có thể biểu diễn điều này với một số n-bit với điều kiện là chúng ta có n mục. Làm thế nào là có thể? Nếu mỗi bit trong số n bit tham chiếu đến một trong các mục n, thì hiển nhiên là chúng ta có thể làm như vậy. Giá trị của n- th bit sẽ là 0, nếu n- th mục sẽ không được đưa vào giải pháp cuối cùng. Trong khi giá trị của nó sẽ là 1, nếu nó sẽ được bao gồm.

Điều đó đang được nói là khá rõ ràng những gì hoán vị đại diện. Nó đại diện cho tất cả các kết hợp có thể có của các mục trong giải pháp cuối cùng. Điều này là rõ ràng, bởi vì mỗi bit có thể có 2 giá trị, hoặc là 0 hoặc 1. Cho rằng chúng ta có n-bit, số lượng các kết hợp có thể là 2^n.

Thực ra, vì lý do này thuật toán này là lực lượng vũ phu thuật toán (chúng tôi thực hiện tìm kiếm toàn diện). Chúng tôi truy cập tất cả các kết hợp có thể để tìm ra kết hợp tốt nhất. Trong vòng lặp sau:

for (int i = 0; i<permutations; i++) 
{ 
    // ... 
} 

bạn lặp qua tất cả các kết hợp có thể.

kết hợp Sau đó foreach, bạn lặp qua các mục bộ sưu tập:

for (int j = 0; j < size; j++) 
{ 
    // Here you check if the item in position j 
    // is included in the current combination. 
    // If it is not, you go to the next value of the loop's variable 
    // and you make the same check. 
    if(((i>>j)&1)!=1) 
     continue; 

    // The j-th item is included in the current combination. 
    // Hence we add it's 
    // value to the total value accumulator and it's weight to 
    // the total weight accumulator. 
    total += Items[j].v; 
    weight += Items[j].w; 
} 

Bây giờ nếu weight là ít hơn so với giá trị giới hạn và tổng giá trị lớn hơn tổng giá trị tốt nhất hiện nay, chúng tôi chọn này kết hợp như hiện tại tốt nhất:

bestPosition = i; 
bestValue = total; 

Cuối cùng, có vòng lặp qua tất cả các kết hợp có sẵn, chúng tôi sẽ có kết hợp tốt nhất.

Sau khi đã tìm thấy kết hợp tốt nhất, chúng tôi phải lặp qua các mục để xem chúng được bao gồm trong kết hợp này.

// The include is a list that will hold the items of the best combination. 
var include = new List<Item>(); 

// We loop through all the available items 
for (int j = 0; j<size; j++) 
{ 
    // If the items is included in the best combination, 
    // add this item to the include list. 
    if (((bestPosition>>j) & 1)==1) 
     include.Add(Items[j]); 
} 

Answer 2

Rõ ràng các phần mã được đề cập là kiểm tra một bit nhất định được đặt, như được chỉ ra bởi các nhận xét. Điều kiện

((i >> j) & 1) != 1 

là đúng nếu và chỉ khi j-bit của i là 0; điều kiện

((bestPosition >> j) & 1) == 1 

là đúng nếu và chỉ nếu j chút -thứ của bestPosition là một. Liên quan đến bức tranh lớn hơn, rõ ràng việc thực hiện sử dụng int để mô hình hóa một tập hợp các mục, trong đó bit j-bit được đặt nếu và chỉ khi j-mục được bao gồm trong bộ này; do đó, kiểm tra thành viên có thể được thực hiện bằng cách kiểm tra bit. Việc thực hiện liệt kê tất cả các tập hợp con của các mục (sử dụng int để đại diện cho chúng) để thực hiện tìm kiếm đầy đủ.

Lưu ý rằng triển khai Delphi cho các bộ sử dụng cùng một cách tiếp cận, nhưng ẩn chỉ mục bit từ mã máy khách.