Thứ Hai, 25 tháng 11, 2013

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


Đề 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].


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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);
    }
 
}