Ai giúp em hướng đi với ạ !! Em cảm ơn!
Bài toán chọn quà tối ưu
bài này có lẽ dùng quy hoạch động (dynamic programing)
tại mảng t với t[2][n] với ý nghĩa t[i][j] là phần thưởng tối đa khi có j món quà, và lượt chọn cuối là lượt chọn i/2 (chẵn/lẽ)
như vậy ta có công thức truy hồi (index từ 0):
t[0][0] = 0, vì lần đầu tiên là lượt lẻ, nên không thể nào coi nó là lượt chẳn được,
t[1][0] = a[0], nếu chọn món quà có index là 0 thì hiển nhiên lượt chọn đó là lượt đầu tiên và là lượt lẻ
t[i][j] = a[j] + max(t[1-i][k]) , với 0 <= k < j và (nếu i = 0, lượt chẵn thì tính max phải có thêm điều kiện a[j] = a[[k])
giải thích, nếu bạn chọn món quà thứ j thì bạn được tổng quà gồm có a[[j] cộng với tổng trước đó bạn đã chọn
tổng trước đó bạn đã chọn chính là lượt ngược lại tối ưu nhất trước đó (nếu món j chẵn thì tổng phần lẻ tối đã hoặc ngược lại)
không có thời gian viết sample nên bạn tự bơi vậy
nếu bạn không biết quy hoạch động là gì thì không có gì để chỉ thêm, phụ thuộc vào sự siêng năng tìm tòi của bạn thôi
có thể tham khảo phần quy hoạch động thêm trong cuốn Giải thuật và lập trình của thầy Lê Minh Hoàng
4 Likes
Vậy có 1 ví dụ như thế này : 2 5 2 6 1 6 2
Nếu theo cách của bác thì
t[0][0]=0 ; t[1][0]=2
t[0][1]=5; t[1][1]=5+0=5
t[0][2]=2+2=4( vì a[2]=a[0]) ; t[1][2]=2+5=7
t[0][3]=6 ; t[1][3]=6+5=11
t[0][4]=1; t[1][4]=1+6=7
t[0][5]=6+11=17( vì a[5]=a[3]) ; t[1][5]=6+6=12
t[0][6]=2+7=9( vì a[6]=a[2]) ; t[1][6]=2+17=19
suy ra đáp số là 19
nhưng đúng ra là 2+2+6+6+2 ( vì nếu chọn 5 ở lượt 1 thì lượt 2 không thể chọn tiếp, nếu chọn 6 ở lượt 1 và lượt 2 thì không thể chọn 5 ở lượt 3 được vì phải chọn từ k+1 đến n-1)
Mong bác giúp đỡ, hoặc chỉ ra chỗ em hiểu sai với ạ!! Cảm ơn nhiều
Sau khi suy nghĩ 1 chút mình sẽ ra bảng như này:
dp:
0 0 4 4 4 16 16
2 5 2 10 5 10 18
Với test case [2, 3, 2, 3, 2]
dp:
0 0 4 6 9
2 3 2 7 8
4 Likes
cảm ơn nha !! Có lẽ do mình không hiểu hết ý của bác trên , khi bằng nhau thì mới cộng ở t[0]
2 5 2 6 1 6 2
số 5 không thể chọn làm món quà thứ 2 được, vì điều kiện là lượt chẵn phải chọn quà có giá trị bằng với lượt trước đó
nên t[0][1] = 0
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?