Giải thuật và lập trình: §3.4. Dãy con có tổng chia hết cho K

Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực

Cho một dãy gồm n (1 <= n <= 1000) số nguyên dương A1, A2, …, An và số nguyên dương k (k <= 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho k.

Input: file văn bản SUBSEQ.INP

  • Dòng 1: Chứa số n
  • Dòng 2: Chứa n số A1, A2, …, An cách nhau ít nhất một dấu cách

Output: file văn bản SUBSEQ.OUT

  • Dòng 1: Ghi độ dài dãy con tìm được
  • Các dòng tiếp: Ghi các phần tử được chọn vào dãy con
  • Dòng cuối: Ghi tổng các phần tử của dãy con đó.

SUBSEQ.INP

SUBSEQ.OUT

10 5

8

1 6 11 5 10 15 20 2 4 9

a[10] = 9

 

a[9] = 4

 

a[7] = 20

 

a[6] = 15

 

a[5] = 10

 

a[4] = 5

 

a[3] = 11

 

a[2] = 6

 

Sum = 80

3.4.1. Cách giải 1

Đề bài yêu cầu chọn ra một số tối đa các phần tử trong dãy A để được một dãy có tổng chia hết cho k, ta có thể giải bài toán bằng phương pháp duyệt tổ hợp bằng quay lui có đánh giá nhánh cận nhằm giảm bớt chi phí trong kỹ thuật vét cạn. Dưới đây ta trình bày phương pháp quy hoạch động:

Nhận xét 1: Không ảnh hưởng đến kết quả cuối cùng, ta có thể đặt: Ai := Ai mod k với mọi i: 1 <= i <= n

Nhận xét 2: Gọi S là tổng các phần tử trong mảng A, ta có thể thay đổi cách tiếp cận bài toán: thay vì tìm xem phải chọn ra một số tối đa những phần tử để có tổng chia hết cho k, ta sẽ chọn ra một số tối thiểu các phần tử có tổng đồng dư với S theo modul k. Khi đó chỉ cần loại bỏ những phần tử này thì những phần tử còn lại sẽ là kết quả.

Nhận xét 3: Số phần tử tối thiểu cần loại bỏ bao giờ cũng nhỏ hơn k

Thật vậy, giả sử số phần tử ít nhất cần loại bỏ là m và các phần tử cần loại bỏ là Ai1, Ai2, …, Aim. Các phần tử này có tổng đồng dư với S theo mô-đun k.

Xét các dãy sau:

Dãy 0 := () = Dãy rỗng (Tổng = 0 (mod k))

Dãy 1 := (Ai1) Dãy 2 := (Ai1, Ai2)

Dãy 3 := (Ai1, Ai2, Ai3)

… …

Dãy m := (Ai1, Ai2, …, Aim)

Như vậy có m + 1 dãy, nếu m >= k thì theo nguyên lý Dirichlet sẽ tồn tại hai dãy có tổng đồng dư theo mô-đun k. Giả sử đó là hai dãy:

Ai1 + Ai2 + … + Aip = Ai1 + Ai2 + … + Aip + Aip+1 + … + Aiq (mod k)

Suy ra Aip+1 + … + Aiq chia hết cho k. Vậy ta có thể xoá hết các phần tử này trong dãy đã  chọn mà vẫn được một dãy có tổng đồng dư với S theo modul k, mâu thuẫn với giả thiết là dãy đã chọn có số phần tử tối thiểu.

Công thức truy hồi:

Nếu ta gọi F[i, t] là số phần tử tối thiểu phải chọn trong dãy A1, A2, …, Ai để có tổng chia k dư t. Nếu không có phương án chọn ta coi F[i, t] =  . Khi đó F[i, t] được tính qua công thức truy hồi sau:

Nếu trong dãy trên không phải chọn Ai thì F[i, t] = F[i - 1, t];

Nếu trong dãy trên phải chọn Ai thì F[i, t] = 1 + F[i - 1, ] ( ở đây hiểu là phép trừ trên các lớp đồng dư mod k. Ví dụ khi k = 7 thì  = 5).

Từ trên suy ra F[i, t] = min (F[i - 1, t], 1 + F[i - 1, t - Ai]).

Còn tất nhiên, cơ sở quy hoạch động: F(0, 0) = 0; F(0, i) =  (với "i: 1 <= i < k).

Bảng phương án F có kích thước [0..n, 0.. k - 1] tối đa là 1001x50 phần tử kiểu Byte.

P_3_03_5.PAS * Dãy con có tổng chia hết cho k

program SubSequence;

const
  InputFile = 'SUBSEQ.INP';
  OutputFile = 'SUBSEQ.OUT';
  maxN = 1000;
  maxK = 50;

var
  a: array[1..maxN] of Integer;
  f: array[0..maxN, 0..maxK - 1] of Byte;
  n, k: Integer;

procedure Enter;
var
  fi: Text;
  i: Integer;

begin
  Assign(fi, InputFile);
  Reset(fi);
  ReadLn(fi, n, k);
  for i := 1 to n do Read(fi, a[i]); Close(fi);
end;

function Sub(x, y: Integer): Integer; {Tính x - y (theo mod k)}
var
  tmp: Integer;

begin
  tmp := (x - y) mod k;
  if tmp >= 0 then Sub := tmp
  else Sub := tmp + k;
end;

procedure Optimize;
var
  i, t: Integer;

begin
  FillChar(f, SizeOf(f), $FF); {Khởi tạo các phần tử f[0, .] đều bằng 255 ()}
  f[0, 0] := 0; {Ngoại trừ f[0, 0] := 0}
  for i := 1 to n do
    for t := 0 to k - 1 do {Tính f[i, t] := min (f[i - 1, t], f[i - 1, Sub(t, ai)] + 1}
      if f[i - 1, t] < f[i - 1, Sub(t, a[i])] + 1 then f[i, t] := f[i - 1, t]
      else
        f[i, t] := f[i - 1, Sub(t, a[i])] + 1;
end;

procedure Result;
var
  fo: Text;
  i, t: Integer;
  SumAll, Sum: LongInt;

begin
  SumAll := 0;
  for i := 1 to n do SumAll := SumAll + a[i]; Assign(fo, OutputFile); Rewrite(fo);
  WriteLn(fo, n - f[n, SumAll mod k]); {n - số phần tử bỏ đi = số phần tử giữ lại}
  i := n; t := SumAll mod k;
  Sum := 0;
  for i := n downto 1 do
    if f[i, t] = f[i - 1, t] then {Nếu phương án tối ưu không bỏ ai, tức là có chọn ai}
    begin
      WriteLn(fo, 'a[', i, '] = ', a[i]);
      Sum := Sum + a[i];
    end
    else
      t := Sub(t, a[i]);
  WriteLn(fo, 'Sum = ', Sum);
  Close(fo);
end;

begin
  Enter;
  Optimize;
  Result;
end.

3.4.2. Cách giải 2

Phân các phần tử trong dãy a theo các lớp đồng dư modul k. Lớp i gồm các phần tử chia k dư i. Gọi Count[i] là số lượng các phần tử thuộc lớp i.

Với 0 <= i, t < k; Gọi f[i, t] là số phần tử nhiều nhất có thể chọn được trong các lớp 0, 1, 2, …, i để được tổng chia k dư t. Trong trường hợp có cách chọn, gọi Trace[i, t] là số phần tử được chọn trong lớp i theo phương án này, trong trường hợp không có cách chọn, Trace[i, t] được coi là -1.

Ta dễ thấy rằng f[0, 0] = Count[0], Trace[0, 0] = Count[0], còn Trace[0, i] với i khác 0 bằng -1. Với i >= 1; 0 <= t < k, nếu có phương án chọn ra nhiều phần tử nhất trong các lớp từ 0 tới i để được tổng chia k dư t thì phương án này có thể chọn j phần tử của lớp i (0 <= j <= Count[i]), nếu bỏ j phần tử này đi, sẽ phải thu được phương án chọn ra nhiều phần tử nhất trong các lớp từ 0 tới i - 1 để được tổng chia k dư .

Từ đó suy ra công thức truy hồi:

P_3_03_6.PAS * Dãy con có tổng chia hết cho k

program SubSequence;

const
  InputFile = 'SUBSEQ.INP';
  OutputFile = 'SUBSEQ.OUT';
  maxN = 1000;
  maxK = 50;

var
  a: array[1..maxN] of Integer;
  Count: array[0..maxK - 1] of Integer;
  f, Trace: array[0..maxK - 1, 0..maxK - 1] of Integer;
  n, k: Integer;

procedure Enter;
var
  fi: Text; i: Integer;

begin
  Assign(fi, InputFile);
  Reset(fi); ReadLn(fi, n, k);
  FillChar(Count, SizeOf(Count), 0); for i := 1 to n do
  begin
    Read(fi, a[i]);
    Inc(Count[a[i] mod k]); {Nhập dữ liệu đồng thời với việc tính các Count[.]}
  end;
  Close(fi);
end;

function Sub(x, y: Integer): Integer;
var
  tmp: Integer;

begin
  tmp := (x - y) mod k;
  if tmp >= 0 then Sub := tmp else Sub := tmp + k;
end;

procedure Optimize;
var
  i, j, t: Integer;

begin
  FillChar(f, SizeOf(f), 0); f[0, 0] := Count[0];
  FillChar(Trace, SizeOf(Trace), $FF); {Khởi tạo các mảng Trace=-1}
  Trace[0, 0] := Count[0]; {Ngoại trừ Trace[0, 0] = Count[0]}
  for i := 1 to k - 1 do for t := 0 to k - 1 do
    for j := 0 to Count[i] do
      if (Trace[i - 1, Sub(t, j * i)] <> -1) and (f[i, t] < f[i - 1, Sub(t, j * i)] + j) then
      begin 
        f[i, t] := f[i - 1, Sub(t, j * i)] + j;
        Trace[i, t] := j;
      end;
end;

procedure Result;
var
  fo: Text;
  i, t, j: Integer;
  Sum: LongInt;

begin
  t := 0;
  {Tính lại các Count[i] := Số phần tử phương án tối ưu sẽ chọn trong lớp i}
  for i := k - 1 downto 0 do 
  begin
    j := Trace[i, t];
    t := Sub(t, j * i);
    Count[i] := j;
  end;

  Assign(fo, OutputFile);
  Rewrite(fo);
  WriteLn(fo, f[k - 1, 0]);
  Sum := 0;
  for i := 1 to n do
  begin
    t := a[i] mod k;
    if Count[t] > 0 then
    begin
      WriteLn(fo, 'a[', i, '] = ', a[i]);
      Dec(Count[t]);
      Sum := Sum + a[i];
    end;
  end;
  WriteLn(fo, 'Sum = ', Sum);
  Close(fo);
end;

begin
  Enter;
  Optimize;
  Result;
end.

Cách giải thứ hai tốt hơn cách giải thứ nhất vì nó có thể thực hiện với n lớn. Ví dụ này cho thấy một bài toán quy hoạch động có thể có nhiều cách đặt công thức truy hồi để giải.

Nguồn: Giáo trình Giải thuật và Lập trình - Lê Minh Hoàng - Đại học sư phạm Hà Nội
» Tiếp: §3.5. Phép nhân tổ hợp dãy ma trận
« Trước: §3.3. Biến đổi xâu
Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực
Copied !!!