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

c - Balo – tiết kiệm thời gian và trí nhớ

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

Theo Wikipedia và các tài nguyên khác mà tôi đã xem, bạn cần ma trậnm[n][W]; n - tổng số phần tử W - Tổng sức chứa của ba lô. Ma trận này trở nên rất lớn, đôi khi quá lớn để có thể xử lý được trong chương trình C. Tôi biết cơ sở của lập trình động là tiết kiệm thời gian bộ nhớ, nhưng có giải pháp nào để tiết kiệm thời gian và bộ nhớ không?

Vấn đề về ba lô: Mã giả của

//Đầu vào:
// Giá trị (được lưu trong mảng v)
// Trọng số (được lưu trong mảng w)
// Số phần tử riêng biệt (n)
// Dung tích ba lô (W)
với j từ 0 đến W thì làm
  m[0, j] := 0
kết thúc cho 
cho tôi từ 1 đến n làm
  với j từ 0 đến W thì làm
    nếu w[i] <= j thì
      m[i, j] := max(m[i-1, j], m[i-1, jw[i]] + v[i])
    khác
      m[i, j] := m[i-1, j]
    end if
  kết thúc cho
kết thúc cho

Giả sử, W = 123456789 và n = 100. Trong trường hợp này, chúng ta nhận được một ma trận rất lớn m[100][123456789]. Tôi đang suy nghĩ về cách triển khai điều này, nhưng điều tốt nhất tôi có thể nghĩ đến là sử dụng một bit (0/1) để lưu những mục nào được chọn. Điều này có thể thực hiện được không? Hoặc có cách nào khác để giải quyết vấn đề này?

int32 -> 32 * 123456789 * 100 bit
one_bit -> 1 * 123456789 * 100 bit

Tôi hy vọng đây không phải là một câu hỏi ngu ngốc và cảm ơn vì những nỗ lực của bạn.

EDIT - Mã C đang hoạt động:

    int dài i, j;
    int dài *m[2];
    m[0] = (long int *) malloc(sizeof(long int)*(W+1));
    m[1] = (long int *) malloc(sizeof(long int)*(W+1));
    for(i = 0; i <= W; i++){
        m[0][i] = 0;
    }

    int đọc = 0;
    int viết = 1;
    int tmp;

    phần trăm int dài = (W+1)*(n)/100;
    bộ đếm int dài = 0;

    for(i = 1; i <= n; i++){
        for(j = 0; j <= W; j++){
            if(w[i-1] <= j){
                m[write][j] = max(m[read][j],(v[i-1]) + m[read][j-(w[i-1])]);
            }khác{
                m[write][j] = m[đọc][j];
            }
            bộ đếm++;
            if(bộ đếm == phần trăm){
                printf("."); //in dấu chấm (.) cho mỗi phần trăm
                fflush(stdout);
                bộ đếm = 0;
            }
        }
        tmp = đọc;
        đọc = viết;
        viết = tmp;
    }

    printf("\n%ld\n", m[read][W]);

    miễn phí(m[0]);
    miễn phí(m[1]);

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

Vấn đề ba lô có thể được sử dụngO(W)không gian để giải quyết.
Ở mỗi bước lặp bạn chỉ cần 2 hàng - mảng tôi [tôi] Và m[i + 1] tình trạng hiện tại.

hiện tại=1
int m[2][W]
đặt NONE cho tất cả các phần tử của m # nghĩa là chúng ta không thể xử lý trạng thái này
m[0][0] = 0 # đây là điểm xuất phát của chúng ta, ban đầu chiếc ba lô trống rỗng

CHO tôi trong [1..n] làm
    next = 3 - current /// chỉ sử dụng 1 hoặc 2 dựa trên chỉ mục hiện tại
    cho j trong [0...W] làm
       m[tiếp theo] [j] = m [hiện tại] [j]
    FOR j trong [w[i]..W] do
       nếu m[current][j - w[i]] không phải là NONE thì # chỉ xử lý các vị trí có thể truy cập
           m[next][j] = max(m[next][j], m[current][j - w[i]] + v[i]);
    current = next; /// hoán đổi trạng thái hiện tại và trạng thái được tạo


Bạn cũng có thể chỉ sử dụng 1 mảng. Đây là mã giả

CHO tôi trong [1..n] làm
    FOR j trong [w[i]..W] do
       m[j] = max(m[j], m[j - w[i]] + v[i]);

Về c - ba lô - tiết kiệm thời gian và dung lượng bộ nhớ, 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/23777255/

31 4 0
Bài viết khuyến nghị: thuật toán - Thuật toán tối ưu để tìm tất cả các chuỗi con tăng dài nhất là gì?
Bài viết khuyến nghị: Cách trả về số lượng mục bằng cách sử dụng tính năng trừu tượng hóa bộ đệm mùa xuân
Bài viết khuyến nghị: Cách lấy giá trị của ô tại vị trí đã chỉ định trong bảng excel trong JAVA
Bài viết khuyến nghị: Cách cải thiện chức năng vectơ python nà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