thảo luận [Học Tập] Topic thuật toán

cuongnm92 said:
Bessie với cow này là usaco rồi. Bài này quy hoạch động O(MxN - 10k x 5k thì vẫn ok). Gọi f[j] [j] là quãng đường mà bò bessie có thể chạy tối đa ở phút thứ i và thể lực là j. Theo đề bài sẽ có 2 lữa chọn.

Giả sử đang có f[j] [j] = quãng đường tối đa mà bò chạy được phút thứ i và có thể lục là j
*) Nếu j > 0 thì có thể chạy được thêm 1 phút (theo đề bài và tốn 1 thể lực)
-> f[i + 1][j - 1] = f[j] [j] + D[i + 1] (D[i + 1] là quãng đường chạy ở phút thứ i + 1
*) Nếu nghỉ thì phút i + 1 sẽ hồi được 1 thể lực
-> f[i + 1][j + 1] = f[j];
Click to expand...
hay quá fen, tui mới học cái quy hoạch động này mà không nghĩ đến, quê quá
 
cuongnm92 said:
Bessie với cow này là usaco rồi. Bài này quy hoạch động O(MxN - 10k x 5k thì vẫn ok). Gọi f[j] [j] là quãng đường mà bò bessie có thể chạy tối đa ở phút thứ i và thể lực là j. Theo đề bài sẽ có 2 lữa chọn.

Giả sử đang có f[j] [j] = quãng đường tối đa mà bò chạy được phút thứ i và có thể lục là j
*) Nếu j > 0 thì có thể chạy được thêm 1 phút (theo đề bài và tốn 1 thể lực)
-> f[i + 1][j - 1] = f[j] [j] + D[i + 1] (D[i + 1] là quãng đường chạy ở phút thứ i + 1
*) Nếu nghỉ thì phút i + 1 sẽ hồi được 1 thể lực
-> f[i + 1][j + 1] = f[j];
Click to expand...
usaco là gì vậy thím?

Tôi nghĩ bài này là 1 kiểu knapsack nhưng có thêm 1 lựa chọn là nghỉ ngơi ( tương đương bag weight < 0 trong bài toán knapsack). Các thím thấy sao?
 
Tuấn Mỏ said:
  • số bị chia lớn nhất của cả dãy ban đầu là 1.
  • nếu xóa số 3 7 7 thì còn lại 8, 6 có số bị chia lớn nhất là 2 (thỏa mãn)
Click to expand...
1634605387886.png


trong lời giải nó dùng cái dãy này, có tác dụng gì nhỉ mn ai biết không, sao không triệt tiêu nốt các số 2 và 3 nhỉ, tại đọc wiki hàm sieve là tìm ra các số nguyên tố
 
Lập Trình Viên Số Khổ said:
View attachment 823635

trong lời giải nó dùng cái dãy này, có tác dụng gì nhỉ mn ai biết không, sao không triệt tiêu nốt các số 2 và 3 nhỉ, tại đọc wiki hàm sieve là tìm ra các số nguyên tố
Click to expand...

show full code thử xem.
Nguyên tắc thì số dương bất kỳ luôn có thể tạo thành từ tích của các số nguyên tố, vd
8 = 1.2.2.2
6 = 1.2.3
7 = 1.7
3 = 1.3

như vậy thì có thể tính được số bị chia lớn nhất
 
1634609755377.png

Các bác giải thích cho em tại sao cái V[i,w] lại bằng max được không? Em đang tìm hiểu dynamic programming mà cái công thức khó hiểu quá :cry:
 
Hỏi ngu phát là giải những bài này ngoài bổ não ra thì còn giúp ích gì không? Vì mình làm lập trình web 6 năm nay chưa đụng đến thuật toán, giờ muốn học thêm
 
thuyduong2007 said:
Bài này dùng dynamic programing nhé. Mặc dù đang nhậu xỉn cũng giải trong vòng 1 nốt nhạc nhé. Tuy nhiên solution chưa thực sự tối ưu.

Python: 
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        self.nums = nums
        return self.findTargetSumWaysRecursive(target)
  
    @cache
    def findTargetSumWaysRecursive(self, target, pos = 0):
        if pos >= len(self.nums):
            return 1 if target == 0 else 0
        return self.findTargetSumWaysRecursive(target - self.nums[pos], pos+1) + self.findTargetSumWaysRecursive(target + self.nums[pos], pos+1)
Click to expand...
bác có thể chuyển bài này sang dùng for/while để e tham khảo được ko.
E đã giải = đệ quy cũng khá giống bác(của e kém hiệu quả hơn) nên muốn thử improve với vòng lặp nhưng mày mò mãi chưa ra được cách khử đệ quy
 
wherehas said:
Hỏi ngu phát là giải những bài này ngoài bổ não ra thì còn giúp ích gì không? Vì mình làm lập trình web 6 năm nay chưa đụng đến thuật toán, giờ muốn học thêm
Click to expand...
Nếu bác làm thuần frontend thì dường như là không liên quan nhiều. Nếu bác có làm backend thì hoạ may sẽ có liên quan một chút.

Lời khuyên của mình là nếu muốn học thuật toán thì đừng nhìn vào lợi ích của nó trong công việc hằng ngày. Nếu bác cảm thấy nó thú vị thì hãy học, còn không khi mang lợi ích ra để ước lượng thì khả năng cao là bác sẽ thấy nó không tương xứng với thời gian bỏ ra.
 
wherehas said:
Hỏi ngu phát là giải những bài này ngoài bổ não ra thì còn giúp ích gì không? Vì mình làm lập trình web 6 năm nay chưa đụng đến thuật toán, giờ muốn học thêm
Click to expand...
Làm web thông thường sẽ chẳng đụng đến bao giờ đâu thím. Lý do là kiến thức về các loại thuật toán kiểu này chỉ phát huy tác dụng khi đụng đến đoạn phải xử lý nhiều data, mà những tình huống này nếu gặp là phải có phương án đẩy vể xử lý ở server.
Chỉ có làm web game hay đi code web framework may ra mới có chỗ để dùng.
 
WoodyTheEvil said:
bác có thể chuyển bài này sang dùng for/while để e tham khảo được ko.
E đã giải = đệ quy cũng khá giống bác(của e kém hiệu quả hơn) nên muốn thử improve với vòng lặp nhưng mày mò mãi chưa ra được cách khử đệ quy
Click to expand...
thay đổi cách tiếp cận thôi bạn, viết đệ quy thì top-down còn muốn khử đệ quy thì bottom-up.

Python: 
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = defaultdict(int)
        dp[0] = 1
        for num in nums:
            tmp_dp = dp
            dp = defaultdict(int)
            for key,value in tmp_dp.items():
                dp[key+num] += value
                dp[key-num] += value
        return dp[target]
Cách này là phiên bản khử đệ quy của cách giái trước đó của t. Tuy nhiên nó chưa thực sự tối ưu. Do nó phải tính hết toàn bộ giá trị có thể sinh ra bởi tập ban đầu. Bản chất là vét cạn thôi, nhưng do giá trị trung gian được lưu lại bởi cái dict nên giảm thiểu được việc tính toán lại. Độ phức tạp của cách này là O(2^n). Do số lượng phần tử của tập ban đầu <= 20 nên cách này k bị timeout.

Cách tối ưu hơn là chuyển về bài toán tìm số tập con có tổng bằng 1 số cho trước.
Giả sử mình có s1 là tổng của các phần tử được thêm dấu +, s2 là tổng của các phần tử được thêm dấu '-'.
s1 + s2 = sum(nums)
s1- s2 = target
=> s1 = (sum + target)/2, s2 = (sum - target)/2
bài toán quy về tìm các tập con có tổng bằng s1 hoặc s2.
Mình sẽ chọn min(s1,s2) làm giá trị cần tìm để giảm không gian tìm kiếm lại, giúp tối ưu hơn.
Ngoài ra +/- 0 thì không làm thay đổi kết quả, do đó mình sẽ đếm số lượng phần tử 0, remove ra khỏi tập ban đầu. Kết quả cuối cùng sẽ *2^numZero. (do mỗi 1 phần tử 0 thì đều có 2 cách chọn +/-). Cái này cũng giúp lời giải tối ưu hơn do giảm được số lượng phần tử cần tính.

C++: 
class Solution {
public: 
    int findTargetSumWays(vector<int>& nums, int target) {
        // get new target
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((sum + target)%2 != 0 || target > sum || target < -sum) return 0;
        int s1 = (sum + target)/2;
        int s2 = (sum - target)/2;
        int new_target = min(s1,s2);
      
        //count number 0 and remove all element equal to 0
        int numZero = count(nums.begin(), nums.end(), 0);
        nums.erase(remove(nums.begin(), nums.end(), 0), nums.end());
      
      
        vector<vector<int>> dp(nums.size()+1, vector<int>(new_target + 1, 0));
        dp[0][0] = 1;
        for (int i = 0;  i < nums.size(); ++i) {
            for (int j = 0;  j <= new_target; ++j) {
                dp[i+1][j] += dp[i][j];
                if (j + nums[i] <= new_target) dp[i+1][j + nums[i]] += dp[i][j];
            }
        }
        return dp.back().back()*pow(2, numZero);
    }
};
 
thuyduong2007 said:
thay đổi cách tiếp cận thôi bạn, viết đệ quy thì top-down còn muốn khử đệ quy thì bottom-up.

Python: 
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = defaultdict(int)
        dp[0] = 1
        for num in nums:
            tmp_dp = dp
            dp = defaultdict(int)
            for key,value in tmp_dp.items():
                dp[key+num] += value
                dp[key-num] += value
        return dp[target]
Cách này là phiên bản khử đệ quy của cách giái trước đó của t. Tuy nhiên nó chưa thực sự tối ưu. Do nó phải tính hết toàn bộ giá trị có thể sinh ra bởi tập ban đầu. Bản chất là vét cạn thôi, nhưng do giá trị trung gian được lưu lại bởi cái dict nên giảm thiểu được việc tính toán lại. Độ phức tạp của cách này là O(2^n). Do số lượng phần tử của tập ban đầu <= 20 nên cách này k bị timeout.

Cách tối ưu hơn là chuyển về bài toán tìm số tập con có tổng bằng 1 số cho trước.
Giả sử mình có s1 là tổng của các phần tử được thêm dấu +, s2 là tổng của các phần tử được thêm dấu '-'.
s1 + s2 = sum(nums)
s1- s2 = target
=> s1 = (sum + target)/2, s2 = (sum - target)/2
bài toán quy về tìm các tập con có tổng bằng s1 hoặc s2.
Mình sẽ chọn min(s1,s2) làm giá trị cần tìm để giảm không gian tìm kiếm lại, giúp tối ưu hơn.
Ngoài ra +/- 0 thì không làm thay đổi kết quả, do đó mình sẽ đếm số lượng phần tử 0, remove ra khỏi tập ban đầu. Kết quả cuối cùng sẽ *2^numZero. (do mỗi 1 phần tử 0 thì đều có 2 cách chọn +/-). Cái này cũng giúp lời giải tối ưu hơn do giảm được số lượng phần tử cần tính.

Code: 
class Solution {
public: 
    int findTargetSumWays(vector<int>& nums, int target) {
        // get new target
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((sum + target)%2 != 0 || target > sum || target < -sum) return 0;
        int s1 = (sum + target)/2;
        int s2 = (sum - target)/2;
        int new_target = min(s1,s2);
      
        //count number 0 and remove all element equal to 0
        int numZero = count(nums.begin(), nums.end(), 0);
        nums.erase(remove(nums.begin(), nums.end(), 0), nums.end());
      
      
        vector<vector<int>> dp(nums.size()+1, vector<int>(new_target + 1, 0));
        dp[0][0] = 1;
        for (int i = 0;  i < nums.size(); ++i) {
            for (int j = 0;  j <= new_target; ++j) {
                dp[i+1][j] += dp[i][j];
                if (j + nums[i] <= new_target) dp[i+1][j + nums[i]] += dp[i][j];
            }
        }
        return dp.back().back()*pow(2, numZero);
    }
};
Click to expand...
Tks bác, để e ngâm cứu, hiện tại e đang kẹt cứng mindset top down vẫn chưa cải thiện được khi làm các dạng bài quy hoạch động
 
Katsura janai said:
View attachment 823133
Các thím có ý tưởng không ạ? Em đọc còn không hiểu đề
Click to expand...
cuongnm92 said:
Bessie với cow này là usaco rồi. Bài này quy hoạch động O(MxN - 10k x 5k thì vẫn ok). Gọi f[j] [j] là quãng đường mà bò bessie có thể chạy tối đa ở phút thứ i và thể lực là j. Theo đề bài sẽ có 2 lữa chọn.

Giả sử đang có f[j] [j] = quãng đường tối đa mà bò chạy được phút thứ i và có thể lục là j
*) Nếu j > 0 thì có thể chạy được thêm 1 phút (theo đề bài và tốn 1 thể lực)
-> f[i + 1][j - 1] = f[j] [j] + D[i + 1] (D[i + 1] là quãng đường chạy ở phút thứ i + 1
*) Nếu nghỉ thì phút i + 1 sẽ hồi được 1 thể lực
-> f[i + 1][j + 1] = f[j];
Click to expand...

Nếu làm theo cách thím @cuongnm92 mình nghĩ sẽ thiếu 1 vế quan trọng là Nếu Bessie bắt đầu nghỉ thì cô chỉ có thể tiếp tục chạy khi thể lực trở lại như M.

Mình đề xuất 1 cách làm sử dụng 2 list là Run hoặc Break để lưu lại kết quả các bước phía trước

C++: 
void CowRun()
{
    const int N = 5;
    const int M = 2;
    int arr[N] = { 5, 3, 4, 2, 10 };

    std::list<std::pair<int, int>> listBreaks = { {0, M} };
    std::list<std::pair<int, int>> listRuns = { {arr[0], M - 1} };

    for (int i = 1; i < N; ++i)
    {
        std::list<std::pair<int, int>> listBreaksNew;
        std::list<std::pair<int, int>> listRunsNew;

        // IF TAKING BREAK
        for (const auto& iter : listBreaks)
        {
            std::pair<int, int> pairDistanceAndPhysical;
            pairDistanceAndPhysical.first = iter.first; // DO NOT INCREASE DISTANCE BECAUSE TAKING BREAK
            pairDistanceAndPhysical.second = __min(M, iter.second + 1); // INCREASE PHYSICAL HEALTH, CANNOT BE BIGGER THAN M

            listBreaksNew.push_back(pairDistanceAndPhysical);
        }

        for (const auto& iter : listRuns)
        {
            std::pair<int, int> pairDistanceAndPhysical;
            pairDistanceAndPhysical.first = iter.first; // DO NOT INCREASE DISTANCE BECAUSE TAKING BREAK
            pairDistanceAndPhysical.second = __min(M, iter.second + 1); // INCREASE PHYSICAL HEALTH, CANNOT BE BIGGER THAN M

            listBreaksNew.push_back(pairDistanceAndPhysical);
        }

        // IF RUNNING
        for (const auto& iter : listBreaks)
        {
            if (iter.second < M) // WHEN BESSIE STARTS TAKING A BREAK, SHE WILLNOT BE ABLE TO RUN AGAIN UNTIL HER PHYSICAL HEALTH IS RECOVERED TO M
                continue;

            std::pair<int, int> pairDistanceAndPhysical;
            pairDistanceAndPhysical.first = iter.first + arr[i]; // INCREASE DISTANCE BY THIS STEP
            pairDistanceAndPhysical.second = iter.second - 1; // DECREASE PHYSICAL HEALTH

            listRunsNew.push_back(pairDistanceAndPhysical);
        }

        for (const auto& iter : listRuns)
        {
            if (iter.second == 0) // IF BESSIE'S PHYSICAL HEALTH IS ZERO, SHE HAS TO TAKE A BREAK
                continue;

            std::pair<int, int> pairDistanceAndPhysical;
            pairDistanceAndPhysical.first = iter.first + arr[i]; // INCREASE DISTANCE BY THIS STEP
            pairDistanceAndPhysical.second = iter.second - 1; // DECREASE PHYSICAL HEALTH

            listRunsNew.push_back(pairDistanceAndPhysical);
        }

        listBreaks = listBreaksNew;
        listRuns = listRunsNew;
    }

    int nMax = 0;

    for (const auto& iter : listBreaks)
    {
        if(iter.second >= M) // ONLY CHECK THE VALUE WHICH'S PHYSICAL HEALTH IS M
            nMax = __max(nMax, iter.first);
    }
}
 

Similar threads

Zuytori
Tiếp nhận đơn xin khai thác 'kho báu' 3 tấn vàng dưới lòng sông ở Bình Thuận
Replies
8
Views
467
yokitonara
Y
Nobitadiradivo
Phê duyệt gần 14.000 tỷ đầu tư tuyến đường nối cao tốc Biên Hòa – Vũng Tàu
Replies
4
Views
363
TraChanhMuoiMe
TraChanhMuoiMe
BaryonicLord
Tính toán kịch bản đánh thuế tiêu thụ đặc biệt, đảo ngược xu hướng tiêu thụ đồ uống có đường
2 3
Replies
47
Views
3K
Cún Xjnh
Cún Xjnh
sankhaukich
Nước cống đen kịt xả ra vịnh Hạ Long
4 5 6
Replies
103
Views
8K
Han sara
Han sara
N
thắc mắc Tìm phim trộm vàng
Replies
2
Views
109
nottelling
N

Share this page

Back
Top