Trung tâm cá nhân
Điều phát hành
từ bỏ
Bài viết phổ biến của tác giả
- Siêu lớp và danh mục iOS/Objective-C
- object-c - -1001 lỗi khi NSURLSession vượt qua httpproxy và /etc/hosts
- java - Nhận địa chỉ url bằng lớp mạng
- ios - Âm thanh không phát trong thông báo đẩy
31
4
Tôi đã gặp phải vấn đề này khi đang thực hiện một dự án và tôi sẽ diễn đạt lại nó bên ngoài phạm vi thực tế của câu hỏi (tôi đoán tôi có thể nói về tầm cỡ và hình dạng của pháo hoa, nhưng điều đó sẽ khiến việc hiểu trở nên phức tạp hơn). Tôi đang tìm một thuật toán (Có thể gần đúng) để giải nó.
tôi có n thùng chứa có kích cỡ khác nhau,m các vật thể có kích thước khác nhauVà Màu sắc khác nhau (các đồ vật có thể có nhiều màu sắc, vì vậy màu sắc của đồ vật thực sự là một tập hợp).
Mục tiêu của tôi là đặt tất cả các đồ vật vào các thùng chứa (tôi đã biết điều này là có thể), do đó giảm thiểu sự đa dạng về màu sắc trên mỗi thùng chứa. "Đa dạng màu sắc được giảm thiểu" có nghĩa là tổng số lượng màu khác nhau trong mỗi vùng chứa là tối thiểu.
Một ví dụ. Tôi có hai vùng chứa kích thước 2 và bốn đối tượng có màu {red}, {red, green}, {blue}, {blue, green}, mỗi đối tượng có kích thước 1. Giải pháp tốt nhất là [{red}, {red, green}], [{blue}, {blue, green}], trong đó tổng số là 2+2=4. Một giải pháp tệ hơn là [{red}, {blue}], [{red, green}, {blue, green}], trong đó tổng độ đa dạng là 2+3=5.
Tôi đoán rằng vấn đề này là NP-hard vì nó nghe có vẻ khó hơn vấn đề về chiếc ba lô: giá trị của đối tượng được chuyển đổi thành giá trị âm và cũng phụ thuộc vào các đối tượng khác trong cùng một vùng chứa. Nhưng tôi không biết làm thế nào để giải quyết vấn đề bằng một giải pháp gần đúng, dù sao thì điều này cũng rất đáng hoan nghênh.
câu trả lời hay nhất
这个问题似乎与 vấn đề đóng thùng Có nhiều điểm chung hơn vấn đề ba lô. hiện hữuvấn đề về ba lô , bạn chỉ có một chiếc ba lô để lấp đầy, nhưng nó có sức chứa mà bạn không thể vượt quá. Và bạn phải làm điều này đồng thời tối đa hóa tổng giá trị của các phần tử bạn chọn đưa vào đó. Ở đây bạn không cần phải sử dụng hết tất cả các yếu tố.
Tuy nhiên, trong bài toán tạo thùng, bạn có nhiều hộp, mỗi hộp có sức chứa. Bạn quan tâm đến việc giảm thiểu số lượng thùng khi đặt từng phần tử vào một thùng. Bạn cũng phải tuân thủ giới hạn dung lượng của từng hộp. Không giống như ba lô, ở đây bạn phải sử dụng hết tất cả các yếu tố.
Trong trường hợp của bạn, bạn cũng đang cố gắng giảm thiểu số lượng hộp, chỉ là chúng không thể ít hơn hai. Và bạn cũng muốn sử dụng hết tất cả các đồ vật. Bạn không nói nhiều về giới hạn dung lượng, nhưng tôi cho rằng bạn cũng phải tôn trọng điều đó. Cho đến nay nó trông rất giống một vấn đề về quyền anh. Bạn có một ràng buộc bổ sung: giảm thiểu số lượng màu trong mỗi vùng chứa.
Bây giờ, tôi sẽ chia sẻ với bạn linh cảm của tôi rằng nó thuộc loại NP-hard - nó có tất cả các yếu tố của việc tạo thùng và một ràng buộc bổ sung. Ví dụ: có thể dễ dàng hiển thị mức giảm từ việc tạo thùng bằng cách sử dụng một phiên bản trong đó các đối tượng đều có màu đỏ. Ta chỉ cần chứng minh bài toán trong NP - tức là có thể kiểm chứng kết quả trong thời gian đa thức. Vâng, chúng tôi có một bằng chứng không chính thức!
Đây là một phương pháp phỏng đoán tham lam có thể hữu ích.
Biểu diễn: Không sử dụng tập hợp, coi độ dài là k chuỗi bit, ở đâu k là số lượng màu sắc khác nhau mà bạn có. Vì vậy, giả sử bạn có 3 màu - đỏ, lục, lam. Bạn có thể biểu thị [blue] 001, [green, blue] là 011, [red] là 100, v.v.
Các mục được sắp xếp theo chuỗi bit màu bằng cách sử dụng chức năng so sánh để tạo ra loại như 001, 010, 100, 011, 110, 111. Bạn có thể thiết kế một hàm so sánh như thế này nhưTrọng lượng HammingChuỗi bit và giá trị thực của nó.
Lưu ý rằng nhiều mẫu màu (chuỗi bit) có thể được chia sẻ bởi nhiều đối tượng. Các đối tượng sẽ xuất hiện dưới dạng các đối tượng liên tiếp trong danh sách được sắp xếp.
Duyệt qua danh sách đã sắp xếp, gán các mục liên tiếp có cùng mẫu màu cho cùng một vùng chứa. Bạn sẽ chuyển từ một màu sang một món đồ nhiều màu.
Bạn tiếp tục làm như vậy cho đến khi hết dung lượng của mỗi hộp.
Một phương pháp khác là bắt đầu đổ đầy thùng theo thứ tự ngược lại. Bắt đầu với đối tượng có nhiều màu sắc nhất. Đổ đầy lại cùng một thùng chứa các đồ vật liên tiếp nếu nó có thể vừa. Khi bạn tìm thấy các phần tử có ít màu hơn, hãy đặt chúng vào các thùng hiện có đã được phủ màu đó.
Cả hai cách tiếp cận đều không tối ưu, nhưng này, chẳng phải chúng ta đã biết điều đó rồi sao? Chúng tôi vừa phác thảo một bằng chứng không chính thức rằng vấn đề là NP-hard.
祝你好运!
Về thuật toán - Giảm thiểu màu sắc: một biến thể của thuật toán ba lô?, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/10244833/
31
4
0
Tôi có câu hỏi về việc giảm thiểu DFA. Vì vậy, tôi đã sử dụng một kỹ thuật nổi tiếng để chuyển đổi một biểu thức chính quy thành NFA và sau đó sử dụng thuật toán goto/closure để xây dựng DFA từ nó. Câu hỏi bây giờ là làm thế nào để giảm thiểu nó? Tôi đã thấy một văn bản về nó ở đây
Đây là mã của tôi "tạo hoạt ảnh" cho TPanel khi con trỏ chuột di chuột qua nó. Tôi cũng có một khối mã để hủy hoạt ảnh của nó. thủ tục Tmain.pStarting1MouseEnter(Người gửi: TOb
Tôi có thanh trượt hình ảnh nơi các hình ảnh thay thế nhau khi hết thời gian chờ. Mình sử dụng hàm setInterval() của jQuery nhưng có một vấn đề nhỏ, sau khi thu nhỏ cửa sổ trình duyệt, hàm này vẫn tiếp tục "hoạt động" và tôi khôi phục vị trí của hình ảnh cửa sổ trình duyệt sao cho
Câu hỏi này đã có câu trả lời ở đây: đã đóng cửa 10 năm trước. Có thể trùng lặp: Làm cách nào tôi có thể dừng nhấp đúp vào thanh tiêu đề cửa sổ
Khi tôi nhấp vào nút thu nhỏ trong ứng dụng Windows Forms của mình, tôi không muốn nó thực hiện hoạt ảnh thu nhỏ Windows cổ điển (cửa sổ rơi xuống thanh tác vụ). Theo như tôi biết, không có sự kiện thu nhỏ nào, tôi chỉ có thể sử dụng thay đổi kích thước, nhưng tôi không biết làm cách nào để phát hiện ra rằng tôi đang
Trước hết - xin lỗi vì tiếng Anh của tôi. Tôi vừa tạo một ứng dụng Android. Nó chứa một số hoạt động và phát nhạc trong nền của ứng dụng này. Khi người dùng rời khỏi ứng dụng theo một cách nào đó (bằng cách nhấp vào nút Quay lại, nút Trang chủ hoặc các phương tiện khác)
Tôi cần trợ giúp viết chương trình cung cấp số điểm tọa độ được chỉ định ở dạng (X, Y). Số điểm sẽ được đưa ra là dòng đầu tiên trong chương trình; nó có thể được máy quét đọc được. Mình cần tính diện tích nhỏ nhất của tất cả các điểm bao gồm các đường x = a và y = b. Vì vậy,
Tôi cần một Hoạt động để quay lại Hoạt động trước đó, nhưng nếu nút này được nhấp lại, nó sẽ tiếp tục Hoạt động cuối cùng. Đây là quy trình bắt buộc: Tôi nhấp vào nút và Hoạt động bắt đầu. Nếu tôi nhấp vào nút "Quay lại"
Khi hoạt ảnh này ngày càng phức tạp hơn, tôi tiếp tục thêm các tham số để chúng có sẵn trên mỗi lệnh gọi lại. Hiện tại có tổng cộng 6. Ví dụ bây giờ tôi muốn tắt hộp nhập liệu trong khi hiển thị thông báo nên tôi phải thêm một phần tử khác - in_element call: M;
Đây là một ứng dụng MFC dựa trên hộp thoại. Tôi không cố ý thêm bất kỳ mã nào cho các nút thu nhỏ, phóng to và khôi phục. Nó có thể hiển thị các nút đó đầu tiên. Nhưng nó biến mất sau khi chạy một thời gian dài. Hoặc có thể giấc ngủ của máy tính đang gây ra sự cố này? tôi không biết
Làm cách nào để tắt chức năng phóng to và/hoặc thu nhỏ của cửa sổ bằng API Windows? Hộp phóng to/thu nhỏ cần được chuyển sang màu xám và tắt, cũng như nhấp đúp vào thanh tiêu đề, kéo lên đầu màn hình, v.v. Câu trả lời hay nhất bạn có thể gọi SetWindowLong/Se
Có chiếc mũ thuật toán nào đã biết có thể giải quyết vấn đề sau: Chúng tôi có một phiên có nhiều cuộc nói chuyện đồng thời. Người dùng nên đánh dấu các buổi nói chuyện mà họ quan tâm, sau đó chúng ta sẽ tạo lịch nói chuyện để hầu hết người của tôi có thể tham dự buổi nói chuyện của họ và giảm thiểu xung đột về lịch trình
Hiện tại tôi chịu trách nhiệm phát triển lớp cửa sổ (C++) cho một dự án nhỏ; mục tiêu là giữ mức độ phụ thuộc ở mức tối thiểu. Việc triển khai Win32/WinAPI hoạt động như mong đợi, tuy nhiên, tôi đang gặp khó khăn khi nói đến Linux/XCB. Tôi biết, tôi có thể kiểm tra "_N
Lập trình Windows C++, làm thế nào để phóng to hoặc thu nhỏ cửa sổ sự kiện? Đối với các sự kiện di chuột xuống, chúng tôi sử dụng cái gì đó như mi.dwFlags = MOUSEEVENTF_LEFTDOWN và sử dụng SendInput()
Tôi đã viết hàm tạo sau có 2 tham số, nếu giá trị (x hoặc y) âm thì nó sẽ được khởi tạo về 0. public Point1 ( int x , int y ) { //nếu một hoặc
Tôi có đoạn mã sau, nếu tôi tối đa hóa cửa sổ điều hướng thì nó hoạt động tốt, nhưng khi tôi thu nhỏ nó thì nó sẽ ngừng hoạt động. Thêm chi tiết: Các chức năng "scrollDown & ScrollTop" ngừng thực thi khi cửa sổ được thu nhỏ. 'sử dụng nghiêm ngặt'
Tôi có một tệp Excel chứa một số macro và biểu mẫu người dùng. Tôi không muốn người dùng truy cập vào tệp mà không cần mật khẩu. Họ chỉ có thể xem biểu mẫu người dùng và nhập dữ liệu thông qua biểu mẫu người dùng. Đây là mã tôi hiện có. Công việc phụ riêng tư
Hiện tại tôi đang cố gắng đào tạo một mạng có cả các tensor có giá trị phức tạp làm đầu vào và đầu ra. Là một hàm mất mát, tôi lấy định mức chênh lệch theo từng điểm giữa đầu ra và giá trị thực. Hàm "thu nhỏ" của tensorflow nhắc các số phức không mong muốn khi tôi cố gắng giảm thiểu hàm mất mát. tôi nghĩ
Chức năng này là chức năng chính tôi muốn tối ưu hóa. Mọi ý tưởng về cách hạn chế việc sử dụng bộ nhớ sẽ rất tuyệt vời. hàm F(len, rNo, n, tỷ lệ = 0,5) s = số không(len);
Làm cách nào để thu nhỏ ứng dụng của tôi bằng cách nhấp vào nút trong ứng dụng trên nền tảng Windows Mobile và Symbian trong Qt? Câu trả lời hay nhất có lẽ QWidget::setWindowState sẽ phù hợp với bạn,
Tôi là một lập trình viên xuất sắc, rất giỏi!