Cái túi

[chipmasteri]

em chưa hiểu về quay lui lắm , có bài tập cô giáo cho để ứng dụng quay lui mà ko nghĩ ra cách giải quyết
xin cho e hỏi :


công dụng của quay lui là gì
và
bài toán cái túi :
cho n đồ vật [ 1.. n ]
đồ vật i có khối lượng k.i
cái túi có thể chứa m (kg)

chọn đồ vật cho vào túi sao cho
1. cái túi có nhiều đồ vật nhất
2. cái túi nặng nhất

[hang_vt]

- bài này QHĐ là tối ưu
- Quay lui :
tập đề cử : a[1] ... a[n]
1. trong vòng try , in ra khi i max
2. trong vòng try , in ra khi t ( = tất cả các phần tử của mảng x + lại ) max

[=========> Bổ sung bài viết <=========]

nếu cần , mình sẽ post code cho bạn

[chipmasteri]

mình rất cần . Bạn có thể post code + chú thích giùm mình được chứ :)



1. trong vòng try , in ra khi i max
2. trong vòng try , in ra khi t ( = tất cả các phần tử của mảng x + lại ) max

làm sao để biết dc max và giữ được dãy các phần tử của max đó

[hang_vt]

const fi='caitui.inp';
fo='caitui.out';

var f:text;
x,kq1,kq2,a:array[0..20] of integer;
n,m,k,vt,max1,max2:integer;

procedure inp;
var i:integer;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
for i:=1 to n do read(f,a[i]);
close(f);
end;

function cal(n:integer):integer;
var t,i:integer;
begin
t:=0;
for i:=1 to n do
t:=t+x[i];
cal:=t;
end;

procedure sol(i:integer);
begin
if i>max1 then
begin
kq1:=x;
max1:=i;
end;
if cal(i)>max2 then
begin
kq2:=x;
max2:=cal(i);
vt:=i;
end;
end;

procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
if k<j then
begin
x[i]:=a[j];
k:=j;
if (cal(i)<=m) and (i<=n) then sol(i);
try(i+1);
k:=0;
end;
end;

procedure pri;
var i:integer;
begin
assign(f,fo);
rewrite(f);
k:=0;
max1:=-maxint;
max2:=-maxint;
try(1);
writeln(f,'CAC DO VAT CUA CAI TUI CO NHIEU DO VAT NHAT :');
for i:=1 to max1 do
write(f,kq1[i],' ');
writeln(f);
writeln(f,'CAC DO VAT CUA CAC TUI NANG NHAT :');
for i:=1 to vt do
write(f,kq2[i],' ');
close(f);
end;

begin
inp; pri;
end.



[=========> Bổ sung bài viết <=========]

- biến k là biến lưu vị trí , để tránh th lặp ( nếu k thix , bạn có thể dùng mảng đánh dấu )
Trong procedure try
- cho chạy tập đề cử ( a[1] ... a[n] )
- nếu vị trí k < vị trí j thì
+ chọn a[j] lưu vào mảng x
+ tính tổng mảng x
+ nếu tổng mảng x <= m ( cái túi chỉ có khối lượng thôi mà ) thì tìm max . Nếu nhận max thì bạn sẽ dùng mảng kq để lưu lại mảng x

[chipmasteri]

cảm ơn hằng
bài nữa nha :

tính a^n mod m ( n~ 1 ngàn tỉ )

[hang_vt]

bạn tách ra :
a^n = (a*a*a...( n lần )) mod k
= ((a mod k) * (a mod k) * ... * ) mod k

[technolt]

a^n = (a^(n div 2)) * (a^(n div 2)) * (a^(n mod 2));
Tách thế kia thế nào đc :@)

[hang_vt]

a^n = (a^(n div 2)) * (a^(n div 2)) * (a^(n mod 2));
Tách thế kia thế nào đc :@)

sao k đc , cứ thử code ik :) Bik :@) àh :D

[chipmasteri]

a^n = (a^(n div 2)) * (a^(n div 2)) * (a^(n mod 2));

công thức này đâu thế :)

[technolt]

@thử thì biết: N 1000 tỉ
@ở đâu ra thế: cái này tự nghĩ ra bạn ạ

[hang_vt]

1000 tỉ nhá . Code đây


const fi='mu.inp';
fo='mu.out';

var f:text;
s,n,k,a:qword;

procedure inp;
begin
assign(f,fi);
reset(f);
readln(f,a,n,k);
close(f);
end;

procedure sol;
var i:longint;
begin
s:=1;
for i:=1 to n do
s:=(s*(a mod k)) mod k;
end;

procedure pri;
begin
assign(f,fo);
rewrite(f);
write(f,s);
close(f);
end;

begin
inp; sol; pri;
end.

[chipmasteri]

nói chung đúng hết all test nhỏ
còn test lớn 1000 tỉ
chạy ko được :(
mà thuật toán hay vậy :)
thật sự mình chưa hiểu lắm
định lý nào thế :P

[songohan2009]

1000 tỉ nhá . Code đây


const fi='mu.inp';
fo='mu.out';

var f:text;
s,n,k,a:qword;

procedure inp;
begin
assign(f,fi);
reset(f);
readln(f,a,n,k);
close(f);
end;

procedure sol;
var i:longint;
begin
s:=1;
for i:=1 to n do
s:=(s*(a mod k)) mod k;
end;

procedure pri;
begin
assign(f,fo);
rewrite(f);
write(f,s);
close(f);
end;

begin
inp; sol; pri;
end.


Bạn này làm hay nhỉ. Thử chạy với n = 1000 tỉ chưa? =]]
i = longint, n = qword, tôi đố bạn for đc i đến 1000 tỉ mà máy ko báo lỗi 201 đấy! ; ))
Chưa kể bạn chạy 1000 tỉ lần thì định chạy trong thời gian bao lâu!? :@)

P.S: bài này có lẽ nên cài đệ quy với độ phức tạp O(log2_N)

[hang_vt]

Bạn này làm hay nhỉ. Thử chạy với n = 1000 tỉ chưa? =]]
i = longint, n = qword, tôi đố bạn for đc i đến 1000 tỉ mà máy ko báo lỗi 201 đấy! ; ))
Chưa kể bạn chạy 1000 tỉ lần thì định chạy trong thời gian bao lâu!? :@)

P.S: bài này có lẽ nên cài đệ quy với độ phức tạp O(log2_N)

k cần đố , 1000 tỉ chạy tốt mà . Mình chạy trên fp . ctrl + f9 1 phát là ra

[songohan2009]

k cần đố , 1000 tỉ chạy tốt mà . Mình chạy trên fp . ctrl + f9 1 phát là ra

Máy tính bạn này tài wo'.
Chạy test đơn giản này thử: 2 1000000000000 2 xem ra bao nhiêu. :@)
Cái kết quả bạn ra là bao nhiêu? Hay lại ra cái bảng exit code = 201 vì cái tội gán LongInt cho QWord. =]]
Chạy được bạn CHỤP MÀN HÌNH rồi đưa ảnh lên đây cho mình xem hộ cái! :@)
Bạn Ctrl + F9 thật hay BỐC PHÉT ra là chạy rồi thế. 8-> =))
Ước j` có được cái bản FPC "chạy được" code kia với n = 10^12 (1000 TỶ). ; )) 8->
Ước j` mình có cái máy "ngon" như máy bạn nhỉ. 8->

[hang_vt]

Máy tính bạn này tài wo'.
Chạy test đơn giản này thử: 2 1000000000000 2 xem ra bao nhiêu. :@)
Cái kết quả bạn ra là bao nhiêu? Hay lại ra cái bảng exit code = 201 vì cái tội gán LongInt cho QWord. =]]
Chạy được bạn CHỤP MÀN HÌNH rồi đưa ảnh lên đây cho mình xem hộ cái! :@)
Bạn Ctrl + F9 thật hay BỐC PHÉT ra là chạy rồi thế. 8-> =))
Ước j` có được cái bản FPC "chạy được" code kia với n = 10^12 (1000 TỶ). ; )) 8->
Ước j` mình có cái máy "ngon" như máy bạn nhỉ. 8->

okie , sr . Mình thử test nhầm a=1000 tỉ , k phải n =1000 tỉ . Mình sửa code lại từ vòng for thành repeat . Code chạy ra , k nhanh lắm


const fi='mu.inp';
fo='mu.out';

var f:text;
s,n,k,a:qword;

procedure inp;
begin
assign(f,fi);
reset(f);
readln(f,a,n,k);
close(f);
end;

procedure sol;
var i:qword;
begin
s:=1;
repeat
s:=(s*(a mod k)) mod k;
inc(i);
until i>n;
end;

procedure pri;
begin
assign(f,fo);
rewrite(f);
write(f,s);
close(f);
end;

begin
inp; sol; pri;
end.


MAI THI R` , CHÚC CÁC BẠN Ở VŨNG TÀU THI TỐT :D

[mini_bestboy]

Hằng ngày mai thi gì vậy ? cũng thi HSG luôn àh ?

[chipmasteri]

hằng nhất rồi :) chúc mừng nhé
kết quả xứng đáng

[hang_vt]

hằng nhất rồi :) chúc mừng nhé
kết quả xứng đáng

sao bik hay zậy ??? Bạn học Vt àh ???

[chipmasteri]

ừ ừ :)
học trường Vũng Tàu