Tìm lỗi sai code bài toán chia kẹo

Thanh_Dat11 · July 21, 2020, 12:19pm

Đề bài toán như sau ạ

Có N gói kẹo, gói thứ i có A_i cái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia N gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất.

Dữ liệu vào trong file “chiakeo.inp” có dạng:

Dòng đầu tiên là số N (N<=100);

Dòng thứ hai là N số A_i (i=1, 2,…, N; Ai <=100).

Kết quả ra file “chiakeo.out” có dạng:

Dòng đầu là độ chênh lệch nhỏ nhất giữa hai phần có thể được.

Dòng hai là một dãy N số,nếu s_i =1 thì gói thứ i thuộc phần 1, nếu s_i =2 thì gói thứ i thuộc phần 2

Mọi người cho em giúp em tìm ra chỗ sai của code em ạ.

#include <bits/stdc++.h>

using namespace std;

int main()

{

    long a[1000],s[1000],d1[1000],d[1000],c[1000];
    long n,m,sum,i,j,k,tu;

    freopen("Chiakeo.inp","r",stdin);
    //freopen("Chiakeo.out","w",stdout);

    sum=0;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
        s[i]=2;
    }

    for (int i=1;i<=1000;i++)
    {
        d[i]=0;
        d1[i]=0;
        c[i]=0;
    }
    d[0]=1;
    d1[0]=1;

    for (int i=1;i<=n;i++)
    {
        for (int j=0;i<=sum-a[i];i++)
        {
            if ((d1[i]==1)&&(d[j+a[i]]==0))
            {
                d[j+a[i]]=1;
                c[j+a[i]]=i;
            }
            d1[i]=d[i];
        }
    }

    //tim phuong an toi uu
    m=sum/2;
    while (d[m]==0)
    {
        m=m-1;
    }
    tu=m;

    //danh dau mang
    while (c[m]>0)
    {
        s[c[m]]=1;
        m=m-a[c[m]];
    }

    for (int i=1;i<=n;i++)
        cout<<s[i]<<" ";
    return 0;
}

nguyen2812 · July 21, 2020, 6:01am

Anh có thể giải thích thuật toán của anh để mọi người dễ hiểu hơn được không ạ. Anh bắt đầu bài này như thế nào, ý tưởng giải của anh là gì? Lỗi sai của anh ở phần thuật toán(nếu chương trình vẫn chạy nhưng cho kết quả sai ) hay chương trình báo lỗi? Anh chạy debug thì thấy đến dòng nào thì bị trục trặc? Anh viết mã giả chưa?
Hmm…
Em thấy anh Gà Coder cmt topic khác mà lại không vào cmt topic của anh nên em nghĩ anh nên kèm thêm ý tưởng của anh vào để mọi người cùng hiểu ạ. Đôi lúc khi hỏi phải thể hiện rằng mình đã làm hết sức mình rồi nhưng vẫn chưa tìm được lỗi sai ở đâu ạ.
Về phần bài toán thì anh thêm thuật toán vào được không ạ vì em không hiểu( nhiều var với loop quá em hơi rối) 🤦 🤦
Có ai hiểu thì cmt giải thích giúp em ạ. Em xin hết.