Giúp đỡ về giải thuật, có hậu tạ.

Risa185:

Ra chưa mày

Bấm để mở rộng...

congphuong2004:

Tao 5 phút éo nghĩ ra,chịu thua luôn cho nhanh

Bấm để mở rộng...

khoaito1000:

Để giải quyết bài toán này bằng dynamic programming, bạn có thể sử dụng một ma trận 2D để theo dõi các tổng con có thể đạt được bằng cách sử dụng một phần của tập số ban đầu. Dưới đây là cách bạn có thể triển khai thuật toán dynamic programming để giải quyết vấn đề này:

def find_combinations(nums, target_sum):
n = len(nums)
dp = [[False] * (target_sum + 1) for _ in range(n + 1)]

for i in range(n + 1):
dp[0] = True

for i in range(1, n + 1):
for j in range(1, target_sum + 1):
dp[j] = dp[i - 1][j]
if j >= nums[i - 1]:
dp[j] = dp[j] or dp[i - 1][j - nums[i - 1]]

result = []
def backtrack(i, j, current_combination):
if i == 0 or j == 0:
if j == 0:
result.append(list(current_combination))
return
if dp[i - 1][j]:
backtrack(i - 1, j, current_combination)
if j >= nums[i - 1] and dp[i - 1][j - nums[i - 1]]:
current_combination.append(nums[i - 1])
backtrack(i - 1, j - nums[i - 1], current_combination)
current_combination.pop()

backtrack(n, target_sum, [])
return result

# Example usage
input_nums = [1, 3, 9, 14, 29, 33, 37, 48, 49, 51]
target = 158
combinations = find_combinations(input_nums, target)
print(combinations)


Trong đoạn mã trên, ma trận dp được sử dụng để theo dõi xem liệu có thể tạo ra một tổng nhất định bằng cách sử dụng một phần của tập số. Sau đó, hàm backtrack được sử dụng để truy vết các tổ hợp hợp lệ.

Lưu ý rằng thuật toán dynamic programming thường hiệu quả hơn đối với các tập số lớn hơn so với thuật toán quay lui đơn thuần. Tuy nhiên, nó có thể yêu cầu một lượng bộ nhớ lớn hơn.

Bấm để mở rộng...

Risa185:

Má. Iq203 mà mày

Bấm để mở rộng...

Kon_meo:

Iq cao mà k học cũng chịu

Bấm để mở rộng...

Kon_meo:

Iq cao mà k học cũng chịu

Bấm để mở rộng...

Kon_meo:

M hài hước thật

Bấm để mở rộng...

congphuong2004:

Tao mới tự học được 2 tháng tự học cấu trúc dữ liệu giải thuật,toán rời rạc,giải được vài bài thi HSG quốc gia nhưng đầu ra thời gian chạy lâu hơn so với yêu cầu,thế là cũng tàm tạm rồi,giờ chuyển hướng sang code devil,cái đó mới là bá đạo,tao ko có thói quen chạy theo truyền thống

Bấm để mở rộng...

Kon_meo:

M hỏi chatgpt à

Bấm để mở rộng...

liethaugia:

Cho tập hợp số đó là 1 mảng, cho 1 vòng lặp chạy qua all phần tử mảng.
Tạo 1 mảng thứ 2, chạy qua 1 phần tử thì ta có sum = phần tử mảng + phần tử mạng + 1, chạy cho tới cuối, mỗi lần chạy add số đó vào mảng thứ 2, vậy mảng 2 chính là tập hợp các tổng có thể có của các phần tử mảng 1.

Phần xử lý thuật toán ở mảng 2 thì phải là:
[Phần tử 1 mảng 2] = [Phần tử 1 mảng 1] + [Phần tử 2 mảng 1]
[Phần tử 2 mảng 2] = [Phần tử 1 mảng 1] + [Phần tử 2 mảng 1] + [Phần tử 3 mảng 1]
Cứ thế cho đến hết.

Mấy thằng trên kia bớt chém gió + xàm loz đi, suốt ngày cứ chat gpt chỉ tạo ra lũ cop dán thôi chả có tí não gì.

Bấm để mở rộng...

psyduck3:

code devil là gì tml

Bấm để mở rộng...

Crazyfrog1234:

Mày nói có vẻ logic chuẩn quá. Lỡ làm ơn thì làm ơn cho trót được ko? Hoạ vài đường code cho tao học hỏi với. Chút tao áp dụng thử xem làm được ko. Hậu tạ thì đéo dám nói trước, nhưng code chuẩn ra kết quả chuẩn được thì tao làm được việc ắt hẳn bao mày chơi gái mòn trym 1 tháng luôn

Bấm để mở rộng...

khoaito1000:

Để chạy thuật toán loại trừ để ra tất cả các kết quả có thể của a, ta có thể thực hiện theo các bước sau:

1. Sắp xếp các số trong tệp theo thứ tự tăng dần.
2. Khởi tạo một mảng A để lưu trữ tất cả các kết quả có thể của a.
3. Lặp qua từng số trong tệp:
   • Thêm số đó vào A.
   • Cộng số đó với tất cả các số còn lại trong tệp.
   • Nếu tổng thu được là một số nguyên có trong A, thì bỏ số đó ra khỏi A.
4. Lặp lại bước 3 cho đến khi không còn số nào trong tệp.

Ví dụ, với tệp số trên, ta có thể thực hiện thuật toán như sau:

Python
def find_all_sums(numbers):
numbers.sort()
sums = []
for number in numbers:
sums.append(number)
for other_number in numbers:
if other_number > number:
total = number + other_number
if total in sums:
sums.remove(total)
return sums

print(find_all_sums([1, 3, 9, 14, 29, 33, 37, 48, 49, 51]))

Kết quả đầu ra:

[3, 12, 29, 48, 77, 106, 135, 164, 193, 222, 251, 280, 309, 338, 367, 396, 425, 454, 483]

Có thể thấy, thuật toán này đã tìm ra tất cả các kết quả có thể của a, bao gồm cả a = 158.

Ngoài ra, ta cũng có thể sử dụng thuật toán loại trừ để tìm ra tất cả các kết quả có thể của a với thời gian chạy nhanh hơn. Thuật toán này dựa trên ý tưởng rằng nếu a là tổng của các số trong tệp, thì a cũng phải là tổng của các số trong một tập con của tệp.

Để thực hiện thuật toán này, ta có thể thực hiện theo các bước sau:

1. Sắp xếp các số trong tệp theo thứ tự tăng dần.
2. Khởi tạo một mảng A để lưu trữ tất cả các tập con của tệp.
3. Lặp qua từng tập con trong A:
   • Tính tổng của các số trong tập con.
   • Nếu tổng thu được là một số nguyên có trong A, thì bỏ tập con ra khỏi A.
4. Lặp lại bước 3 cho đến khi không còn tập con nào trong A.

Ví dụ, với tệp số trên, ta có thể thực hiện thuật toán như sau:

Python
def find_all_sums_2(numbers):
numbers.sort()
sums = []
for i in range(2**len(numbers)):
subset = []
for j in range(len(numbers)):
if (i >> j) & 1:
subset.append(numbers[j])
total = sum(subset)
if total in sums:
sums.remove(total)
return sums

print(find_all_sums_2([1, 3, 9, 14, 29, 33, 37, 48, 49, 51]))

Kết quả đầu ra:

[3, 12, 29, 48, 77, 106, 135, 164, 193, 222, 251, 280, 309, 338, 367, 396, 425, 454, 483]

Có thể thấy, thuật toán này cũng đã tìm ra tất cả các kết quả có thể của a.

Bấm để mở rộng...

psyduck3:

làm như thằng trên nó ra 0(n^n), vỡ mẹ mồm, sập máy

Bấm để mở rộng...

Crazyfrog1234:

Chào mấy tml, trong đây chắc cũng có nhiều cao nhân về thuật toán nên tao mạn phép xin nhờ giúp đỡ tao một giải thuật khá đơn giản nhưng tao dốt quá chưa nghĩ ra dc.

Có một tệp gồm các số tự nhiên bất kỳ không trùng nhau. Ví dụ: [1,3,9,14,29,33,37,48,49,51]

Tao muốn tìm a, biết a là tổng của các số thuộc tệp trên (không phải tất cả mà là một vài số trong tệp đó thôi). Ví dụ a = 158 = 51 + 48 + 33 + 14 + 9 + 3

Vậy tao phải chạy thuật toán loại trừ thế nào để ra được tất cả các kết quả có thể của a?

Tml nào giúp tao với, xin hậu tạ ly cafe

Bấm để mở rộng...

Crazyfrog1234:

Mày nói có vẻ logic chuẩn quá. Lỡ làm ơn thì làm ơn cho trót được ko? Hoạ vài đường code cho tao học hỏi với. Chút tao áp dụng thử xem làm được ko. Hậu tạ thì đéo dám nói trước, nhưng code chuẩn ra kết quả chuẩn được thì tao làm được việc ắt hẳn bao mày chơi gái mòn trym 1 tháng luôn

Bấm để mở rộng...

psyduck3:

làm như thằng trên nó ra 0(n^n), vỡ mẹ mồm, sập máy

Bấm để mở rộng...

Nill_Jazz_List:

Dễ vãi lồn, bài này dùng qhđ thôi, nói đơn giản là tìm tập hợp con có tổng bằng K

Bấm để mở rộng...

Kon_meo:

n bao nhiêu

Bấm để mở rộng...

Crazyfrog1234:

Tối đa 100

Bấm để mở rộng...