Bài này có thể giải bằng Duyệt quay lui:
- Xét tất cả các phương án chia (các gói) kẹo cho Tí, số còn lại sẽ là của Tèo. Nếu chia cho Tí các gói có tổng số kẹo là thì số kẹo Tèo nhận được sẽ là với . Do đó, chênh lệch số kẹo sẽ là . Trong các phương án chia kẹo như vậy, ta tìm phương án có chênh lệch số kẹo nhỏ nhất.
- Mỗi phương án chia kẹo cho Tí sẽ là một véc-tơ , trong đó . Khi đó, số kẹo Tí nhận được sẽ là .
Ta dễ dàng cài đặt thủ tục Backtracking để duyệt tất cả các phương án chia kẹo như trên.
- ĐPT:
Tổng cộng 1 trả lời
#include <bits/stdc++.h>
using namespace std; int n, a[100], x[100], s=0, c, t, ra[1000], q= 10000, o; void keo(int i) { if(i>n) { t=0; for(int k=1;k<=n;k++) { t=t+a[k]x[k]; } if(abs(s-2t)<q) { o=1; q=abs(s-2*t); for(int l=1;l<=n;l++) { if(x[l]==1) { ra[o]=a[l]; o++; } } } } else { for(int j=0;j<=1;j++) { x[i]=j; keo(i+1); } } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; s=s+a[i]; } keo(1); for(int y=1;y<=o-1;y++) cout<<ra[y]<<" " ; return 0; }