[Thuật toán – Java]Chia tiền lẻ sử dụng Quay lui

Tháng Năm 30, 2013 nguyenvanquan7826 LT Java, Thuật toán 2 responses

Đề bài yêu cầu liệt kê ra các trường hợp có thể khi chia số tiền N ra thành các đồng tiền mệnh giá a[i].

import java.util.Scanner;

class java_chiatien
{
    int n, N, a[], b[], sum=0;
    public void input()
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Nhap so tien can chia: ");
        N = in.nextInt();
        System.out.print("Nhap so loai tien le: ");
        n = in.nextInt();
        a = new int [n];
        b = new int [N];
        for (int i=0; i<n; i++)
        {
            System.out.printf("Nhap loai tien thu %d : ",i+1);
            a[i] = in.nextInt();
        }
        in.close();
    }
    public void chiatien(int i)
    {
        for (int k = 0; k < n; k++)
        {
            b[i] = a[k];
            if (i==0 || (i >0 && b[i] >= b[i-1]))
            {
                sum += b[i];
                if (sum <= N)
                {
                    if (sum == N)
                    {
                        for (int l=0; l<=i; l++)
                            System.out.print(b[l]+ "  ");
                        System.out.print("n");
                    }
                    else
                        chiatien(i+1);
                }
                sum -= b[i];
            }
        }

    }
    public static void main(String[] agrs)
    {
        java_chiatien ct = new java_chiatien();

        ct.input();
        System.out.print("nCac cach chia tien :n");
        ct.chiatien(0);
    }

}