Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

android - thuật toán - Lập trình động và ba lô 0/1

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 03:50:56 35 4
mua khóa gpt4 Nike

Tôi gặp một số khó khăn khi hiểu lập trình động, mặc dù tôi đã đọc qua rất nhiều tài nguyên để cố gắng hiểu.

Tôi hiểu ví dụ về lập trình động được đưa ra bằng thuật toán Fibonacci. Tôi hiểu rằng nếu bạn sử dụng phương pháp chia để trị thì bạn sẽ giải được một số bài toán con nhiều lần, trong khi lập trình động giải quyết vấn đề này bằng cách giải các bài toán con chồng chéo này, nhưng chỉ một lần (và lưu trữ chúng để tham khảo sau này). lập trình động trong lớp bằng cách sử dụng bài toán chiếc ba lô 0/1 làm ví dụ, nhưng tôi không thực sự hiểu ví dụ này hoặc cách nó minh họa lập trình động hoặc nó giống với ví dụ Fibonacci như thế nào.

Dưới đây là các slide có liên quan:

nhập mô tả hình ảnh ở đây

nhập mô tả hình ảnh ở đây

nhập mô tả hình ảnh ở đây

nhập mô tả hình ảnh ở đây

Hầu hết tôi đều hiểu chuyện gì đang xảy ra cho đến trang trình bày cuối cùng có ghi f(i,y) = max{....}

Tôi đã tìm thấy gì? Tại sao tôi lại tìm được giá trị lớn nhất của bất cứ thứ gì? Quan trọng nhất, điều này có liên quan gì đến lập trình động? Tôi không hiểu mối quan hệ này, giống như tôi đã hiểu khi xét đến ví dụ Fibonacci. Thực lòng tôi không biết vấn đề về chiếc ba lô này có liên quan gì đến lập trình động vì nó thậm chí không thể so sánh được với việc sử dụng ví dụ Fibonacci để minh họa cho lập trình động. Giống như tôi không thể thấy bất kỳ sự tương đồng hay bất cứ điều gì, nó thực sự không có nhiều ý nghĩa đối với tôi

câu trả lời hay nhất

Lập trình động chỉ đơn giản là xác định vấn đề theo các vấn đề con đơn giản hơn.

Đối với dãy Fibonacci, chúng ta định nghĩa bài toán theo hai thuật ngữ nhỏ hơn.

Trong trường hợp này, chúng ta xác định một bài toán với một số mục nhất định và một dung lượng nhất định theo một bài toán con chứa ít mục hơn và có thể có dung lượng nhỏ hơn.

Chúng tôi bắt đầu tính toán lợi nhuận cho tối đa 1 mặt hàng và theo công suất. Sau đó, chúng tôi tính toán lợi nhuận cho tối đa 2 mặt hàng và mỗi công suất. Sau đó, chúng tôi thực hiện việc này cho tối đa 3 mục, rồi 4 mục, v.v. Vì chúng ta đã xác định một bài toán theo các bài toán con có ít mục hơn nên chúng ta có thể chỉ cần tra cứu những gì chúng ta đã tính toán để xác định bất kỳ giá trị nào với 2, 3, 4 mục, v.v.

Có thể hữu ích khi coi đây như một lưới 2D vật lý, nơi bạn điền các giá trị từ hướng này sang hướng khác và mỗi lần bạn chỉ nhìn vào hướng mà tất cả các giá trị đã được điền.

Có các bài toán con chồng chéo nhau vì trong một trường hợp chúng ta sử dụng cùng một dung lượng và trong trường hợp khác chúng ta sử dụng một dung lượng nhỏ hơn. Dung lượng nhỏ hơn đôi khi phù hợp với các bài toán con khác nhau kiểm tra cùng một dung lượng. Nói cách khác, một vấn đề f(i+1, j) sẽ bằng với câu hỏi khác f(i+1, y - w_i). Ví dụ, bạn có thể thấy f(11, 5) Xuất hiện ở hai nơi:

f(10, 8) = max(f(11, 8), f(11, 5) + 77) // w_i = 3
f(10, 5) = max(f(11, 5), f(11, 2) + 77)

Trong trường hợp này, chúng tôi có X Đã tính toán f(11,X), vì vậy chúng ta chỉ cần tìm những giá trị này.

Tôi nhận thấy rằng chúng tôi đã tăng Tôi Có một chút khó hiểu khi định nghĩa vấn đề là f(i, j) = ...f(i+1, X)... Và f(n,X) Vì vậy hãy chứa tối đa 1 mục thay vì sử dụng giảm dần Tôi và chứa tối đa 1 mụcf(1,X). Nhưng đó chỉ là ngữ nghĩa và không thay đổi được vấn đề theo bất kỳ cách nào.

Chi tiết kỹ thuật được giải thích

f(i,y) là một mục đi kèm Tôi đến n Lợi nhuận tối đa của một tập hợp con của , với công suất là y .

Bây giờ chúng ta có thể định nghĩa nó để bao gồm hoặc loại trừ các mục Tôi, sau đó lấy vật phẩm i+1 đến n lợi nhuận tối đa.

Khi chúng tôi loại trừ các mục Tôi , điều này không làm thay đổi trọng số, vì vậy chúng ta chỉ có thể xem xét lợi nhuận tối đa cho cùng một công suất, tức là f(i+1, y) và lợi nhuận không thay đổi.

Khi chúng tôi bao gồm dự án Tôi Điều này sẽ thay đổi trọng lượng của đồ vật, đặc biệt là Tôi Trọng lượng của w_i, vì vậy chúng ta phải tìm f(i+1, y - w_i). Nhưng sau đó chúng tôi cũng nhận được hàngTôilợi nhuận, vì vậy chúng ta cần cộng lợi nhuận của nó, nghĩa làp_i.

Bây giờ, vì muốn có lợi nhuận tối đa nên chúng ta phải tìm giá trị lớn nhất của hai giá trị này, cho ta:

f(i, y) = max{f(i+1, j), f(i+1, y - w_i) + p_i}

Nếu bạn vẫn không thể tìm ra, tôi khuyên bạn nên tự mình xây dựng một ví dụ để làm điều đó - không có lời giải thích nào để thấy nó thực sự hoạt động và hãy sử dụng nó để có trực giác về lý do tại sao chúng ta làm mọi việc theo cách chúng ta làm. LÀM.

Về thuật toán - lập trình động và ba lô 0/1, 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/23335783/

35 4 0
Bài viết khuyến nghị: thuật toán - Thuật toán hạt
Bài viết khuyến nghị: Phiên liên tục sử dụng JDBC và Tomcat
Bài viết khuyến nghị: Đối tượng với XML, khả năng tương thích ngược và xuôi
Bài viết khuyến nghị: java - Ứng dụng của tôi tiếp tục chạy GC đầy đủ!
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress