Bài tập quay lui chia mảng thành các nhóm nhỏ có tổng bằng nhau

#1

Cho dãy A gồm n số (1 < n <= 10) và một số nguyên dương K (1 < K <= n/2). Hãy tìm cách chia dãy số A thành K nhóm sao cho tổng của chúng bằng nhau.
Dữ lieu vào gồm 2 dòng, dòng đầu chứa 2 số nguyên n và K, dòng thứ 2 ghi n số của dãy A. Dữ liệu ra gồm K dòng, mỗi dòng là các số thuộc cùng một nhóm, nếu không chia được thì ghi -1
Vd:

Input:
5 3
1 4 6 9 10

Output:
1 9
4 6
10

Em mới học đệ quy quay lui mà thầy cho bài này thấy khoai quá mọi người ạ, ai có ý tưởng nào giúp em với :cry:

3 Likes
#2

:rofl: ý tưởng ban đầu của mình :

  1. tổng các số trong dãy lại rồi chia cho K ( vừa lấy dư vừa lấy thương)
    ->dư khác 0 => ghi ra -1
    -> dư =0 => sang bước 2
    2.đưa về bài toán subset sum rồi làm
5 Likes
#3

Ra vậy, mình làm được rồi, tks bạn nhé :grin:

#4

chào bạn, bạn đã làm ra đề chưa ?
bạn cho có thể giải thích cách làm ( hướng đi) cho mình đc ko ?
Cám ơn bạn

#5

bạn có thể cho mình xin chương trình để mình tham khảo được ko ?
Mail : [email protected]

#6

Với n<=10 ta có thể tính tổng từng tổ hợp :smiley: có 1023 tổ hợp thôi. Ngoài ra thì đúng vậy, cũng là quay lui tìm tổng. Cụ thể nó là nếu muốn tìm tập con của S có tổng s, ta chọn i bất kì rồi tìm tập con của S \ {a[i]} có tổng s - a[i].

Hình như có cách chuyển trạng thái trong O(1) nữa.

2 Likes
#7

Tính tổng hết tất cả các tổ hợp, sau đó từng tổng chia k số nhóm . Nếu tổng nào chia hết số k thì mình sẽ chọn , không chia hết thì mình bỏ chọn.
vd : tổng 1 4 6 9 10 bằng 30 chia k = 3 bằng 10 .
lấy 10 đem so sánh nhóm tổng bằng 10 mình sẽ chọn .
Phải vậy không bạn ?

1 Like
#8

nhưng mình vẫn chưa biết quay lui làm sao ???
code của mình

int tong( int a[], int n)
{
    int i,s;
    for(i=0,s=0;i<n;i++) 
	s=s+a[i];
    return s;
}

void quaylui (void) {
int s = tong(a,n);
   printf("\ntong la %5d",s);
 int TgK = s/4 ;          // chia làm 4 nhom
	printf("\ntong la %5d", TgK);
}
#9

:expressionless: đồng chí nên đọc cái thuật toán quay (backtrack) với vét cạn(bruteforce) còn code thì mình nghĩ nó sai :3

2 Likes
#10

em thử làm lại
mà nó không có in ra được gì hết

#include <stdio.h>
#include <conio.h>
int  S[100], n, k, count = 0;
int tong( int a[], int n)
{
    int i,s;
    for(i=0,s=0;i<n;i++) 
	s=s+a[i];
    return s;
}
void Result(void){
 int i; count++;
 printf("\n Tap thu %d:", count);
 for (i = 1; i <= k; i++){
  printf("%3d", S[i]);
 }
 getch();
}
void quaylui (int i) {
for(int j=1;j< n; j++)
{if(tong(S,n)/k)
S[i]=j;
if(i=k) 
Result;
else quaylui(i+1);
}
}
int main()
{
int i =0;
int k =3;
int S[]={1, 3, 5, 2, 7, 4};
int	n = sizeof(S) / sizeof(S[0]);
quaylui(i);
return 0;
}
#11

:v hàm có xuất cái gì đâu, ko có printf thì ai thấy output

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?