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

Crazyfrog1234

Crazyfrog1234

Thôi vậy thì bỏ
New-Zealand
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 :(
 
Vấn đề này thuộc loại bài toán tìm tổ hợp của một tập số sao cho tổng của chúng bằng một số cụ thể (a). Bạn có thể giải quyết vấn đề này bằng cách sử dụng thuật toán tìm kiếm quay lui (backtracking) hoặc thuật toán động (dynamic programming) để liệt kê tất cả các tổ hợp có thể của a bằng các số trong tập đã cho.

Dưới đây là một ví dụ về cách bạn có thể triển khai thuật toán đệ quy để giải quyết vấn đề này:

def find_combinations(nums, target_sum):
def backtrack(start, target, current_combination):
if target == 0:
result.append(list(current_combination))
return
for i in range(start, len(nums)):
if nums <= target:
current_combination.append(nums)
backtrack(i + 1, target - nums, current_combination)
current_combination.pop()

result = []
backtrack(0, 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, hàm find_combinations sử dụng một hàm đệ quy backtrack để thử tất cả các tổ hợp có thể của các số từ mảng nums để có tổng bằng target_sum. Các tổ hợp hợp lệ được thêm vào danh sách result.

Lưu ý rằng đây chỉ là một cách triển khai cơ bản. Thuật toán này có thể không hiệu quả cho các tập số lớn và mục tiêu lớn. Trong thực tế, bạn có thể cân nhắc sử dụng thuật toán tối ưu hơn như dynamic programming để giải quyết vấn đề này một cách hiệu quả hơn, nhất là khi tập số và mục tiêu lớn.
 
Để 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.
 
Đầu tiên xác định số tổng là chẵn hay lẻ.
Sau đó tìm các cặp số cộng với nhau ra chẳn hay lẻ.
Típ tới xét số đó hàng chục hay trăm để lọc bớt các số hạng quá lớn hay quá.
R sau đó tau cx đéo bik tau đang nghĩ j lun
 
khoaito1000:
Vấn đề này thuộc loại bài toán tìm tổ hợp của một tập số sao cho tổng của chúng bằng một số cụ thể (a). Bạn có thể giải quyết vấn đề này bằng cách sử dụng thuật toán tìm kiếm quay lui (backtracking) hoặc thuật toán động (dynamic programming) để liệt kê tất cả các tổ hợp có thể của a bằng các số trong tập đã cho.

Dưới đây là một ví dụ về cách bạn có thể triển khai thuật toán đệ quy để giải quyết vấn đề này:

def find_combinations(nums, target_sum):
def backtrack(start, target, current_combination):
if target == 0:
result.append(list(current_combination))
return
for i in range(start, len(nums)):
if nums <= target:
current_combination.append(nums)
backtrack(i + 1, target - nums, current_combination)
current_combination.pop()

result = []
backtrack(0, 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, hàm find_combinations sử dụng một hàm đệ quy backtrack để thử tất cả các tổ hợp có thể của các số từ mảng nums để có tổng bằng target_sum. Các tổ hợp hợp lệ được thêm vào danh sách result.

Lưu ý rằng đây chỉ là một cách triển khai cơ bản. Thuật toán này có thể không hiệu quả cho các tập số lớn và mục tiêu lớn. Trong thực tế, bạn có thể cân nhắc sử dụng thuật toán tối ưu hơn như dynamic programming để giải quyết vấn đề này một cách hiệu quả hơn, nhất là khi tập số và mục tiêu lớn.
Bấm để mở rộng...
AI nhanh hơn cả tao
 
Để 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.
 
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...
@Crazyfrog1234
 
Sao tao nhìn 3 phút rồi éo hiểu quy luật là gì,diễn giải đơn thuần thôi,đừng lôi thuật toán giải sẵn ra vội
 
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...
Đây sát nhất với đề bài của tao này. Tối nay về tao code python thử xem được ko. Thành công thì tao bắn cho ly cafe hậu tạ nhé
 
1,3,9,14,29,33,37,48,49,51 dãy này éo hiểu theo quy luật gì luôn,tao chịu nha,5 phút éo nghĩ ra,coi như bỏ chịu thua
 
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...
Mà khoan, đéo đúng lắm, ví dụ a = 13, tức a = 1 + 3 + 9 thì lại k có trong tệp kết quả. Ko dc ko dc, thiếu chỗ nào rồi
 
Bạn có thể sử dụng thuật toán quy hoạch động để giải quyết vấn đề này. Thuật toán này sẽ giúp bạn tìm ra tất cả các tổng có thể của các phần tử trong tập hợp số tự nhiên của bạn
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print("sum(%s)=%s" % (partial, target))
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers
remaining = numbers[i+1:]
subset_sum(remaining, target, partial + [n])
 
buonnguqua:
Đù, cứ tưởng bật nhầm tab Voz :waaaht:
Bấm để mở rộng...
Học thuật toán học đủ đến mức hiểu giao tiếp với máy tính ra sao thôi,đâm đầu vào mấy cái đánh đố nâng cao làm cái Lồn gì,éo áp dụng được gì ra tiền thì ăn cứt
 
Chào bạn! Vấn đề của bạn là bài toán tìm tất cả các tổng con có thể từ một tập hợp con của tập số đã cho. Để giải quyết vấn đề này, chúng ta có thể sử dụng một thuật toán quay lui (backtracking) để duyệt qua tất cả các tập hợp con của tập số ban đầu và tính tổng của mỗi tập hợp con đó.

Dưới đây là một đoạn mã Python thực hiện điều này:

pythonCopy code
def find_subset_sums(nums, target_sum):
def backtrack(start, current_sum, current_subset):
if current_sum == target_sum:
result.append(current_subset[:])
return
for i in range(start, len(nums)):
if current_sum + nums <= target_sum:
current_subset.append(nums)
backtrack(i + 1, current_sum + nums, current_subset)
current_subset.pop()

result = []
backtrack(0, 0, [])
return result

# Example usage
nums = [1, 3, 9, 14, 29, 33, 37, 48, 49, 51]
target_sum = 158
result = find_subset_sums(nums, target_sum)
for subset in result:
print(subset)

Trong mã trên, hàm find_subset_sums sẽ trả về tất cả các tập hợp con có tổng bằng target_sum. Hàm backtrack thực hiện việc duyệt qua các tập hợp con bằng cách thử tất cả các phần tử trong tập số ban đầu.

Lưu ý rằng việc tìm tất cả các tập hợp con của tập số có thể tạo thành một tác vụ tốn thời gian với tập số lớn. Do đó, hãy cân nhắc sử dụng mã trên cho các tập số có kích thước nhỏ hơn.
 
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ì.
 
Đăng nhập hoặc Ghi danh để trả lời

Có thể bạn quan tâm

đéo có hình chó nó tin
Đồng Nai lập Tổ giúp việc giải phóng mặt bằng dự án khu đô thị ven sông
Trả lời
1
Lượt xem
58
đéo có hình chó nó tin
đéo có hình chó nó tin
N
Live Min Hưng thành công trung lưu giải ngân yêu nước kế thừa cựu Gấu Bông thành công, phái độc lập phối hợp phát triển, giúp DN người dân...
Trả lời
0
Lượt xem
44
nguoivehuu
N
N
Live Mới ở tù ra, làm các cựu phó Thống đốc lên ruột bằng trading forex khớp 🇻🇳, họ hạnh phúc xúc động giải quyết, conan giúp, 🕵 Quân Đội cũng thấy
Trả lời
0
Lượt xem
67
nguoivehuu
N
N
Live Hoàng Giáp: xàmvn 🇻🇳 một chút giúp Ubck 🇻🇳, Vtv1x100 Tckd tăng 50 điểm ah, mình tận 100, thế giới thực 🇻🇳 mình giải quyết tốt 7 tháng 👍
Trả lời
2
Lượt xem
135
nguoivehuu
N
N
Live Lý thuyết Nobel, 🇻🇳 giải sắp hàng được 3 tổ chức lớn nhất trao giải khuyến khích, các bạn giúp một phần phát triển 🇻🇳, lý thuyết tâm lý tôn trọng:
Trả lời
8
Lượt xem
97
nguoivehuu
N
hầm bà lằng
Ai giải thích giúp e với
Trả lời
0
Lượt xem
37
hầm bà lằng
hầm bà lằng
Hoàng Tử DiNa
Có Video Cảm ơn Giải phóng quân đã giúp dân làng an tâm khi dẹp nạn Thổ phỉ Đỏ lén lút ăn cắp vào ban đêm
Trả lời
1
Lượt xem
158
xetaxi
X
Top