Thật sự chả hiểu cái gì luôn ...mọi người gợi ý cái

thế này .....thầy em phán cho cái đề (C++)

Nhìn vào em choáng quá ...hic hic có ai hiểu gợi ý giúp em

 

Bài này có 2 tham số là M(số tiền) và N(số lĩnh vực). Ông phải chia nhỏ M thành nhiều a (số tiền kinh doanh vào 1 lĩnh vực) và tìm k trong khoảng 1 đến N sao cho tổng lợi nhuận (tổng của tất cả các Lak đó. Tôi cũng không hiểu Lak này là gì) đạt được là max.

 

Ta tạo 1 mảng Lak[][] 2 chiều( N x 2), trong đó Lak[2] là lợi nhuận khi đầu tư số tiền Lak[1] vào lĩnh vực thứ i, bài toán sẽ quay về tính tổng lớn nhất các giá trị sao cho tổng nhãn của nó( số tiền Lak[1]) nhỏ hơn hay bằng số tiền M, bạn có thể sử dụng thuật toán qui hoạch động hay thuật toán duyệt mảng bình thường để làm bài toán này.

 

Gọi F[i,j] là số lãi nhiều nhất có thể lấy được bằng cách chọn trong số công việc từ 1 ---> i với số tiền phải đầu tư lớn nhất là j.
lập mảng Lak là lợi nhuận của từng công việc
A là mảng để đầu tư cho mỗi công việc

Mã:

For i:=1 to n do
     for j:=0 to M do
          begin
               F[i,j]:=F[i-1,j];
               If (j>=a[i]) and (F[i,j] < F[i-1,j-a[i]] + Lak[i]) then
                  F[i,j] :=F[i-1,j-a[i]] + Lak[i]
          end; 
Bây giờ ta chỉ cần  truy vết tìm nghiệm tối ưu
Bằng cách đi ngược lại 
Xét xem F[n,M] có <> F[n-1,M] hay không
Nếu khác thì viết n ra ngoài màn hình và đặt M:=M-a[n];
và lại giảm n và xét tiếp cho đến khi n=0

 

Cái này có mùi của môn Lý thuyết đồ thị hen ? Không biết nói đúng không nữa .