01/10/2018, 15:34

Đổi tiền bằng backtracking

Mình muốn liệt kê các cách đổi tiền bằng các tờ VND có sẵn. Input là tiền cần đổi

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>

int VND[9] = { 1,2,5,10,20,50,100,200,500 };
int t = 8;
void doiTienLe(int tien, int tienle)
{
	tienle = VND[t];
	if (tienle == VND[0])
		printf(" %d
", tien * 1000);
	else
	{
		for (int i = 0; i <= tien / tienle; i++)
		{
			if (i == 0)
				continue;
			printf("%d * %d +", tienle * 1000, i);
			
			t--;
			doiTienLe(tien - tienle * i, VND[t]);
			t++; //quay lui
		}
	}

}

int main()
{
	printf("Nhap vao so tien muon doi: ");
	int tien;
	scanf("%d", &tien);
	doiTienLe(tien / 1000, VND[t]);

	_getch();
	return 0;
}

Trên là code của mình, nhưng chạy không ra kết quả mong muốn
Mn người góp ý giúp mình với ạ

NGUYỄN ĐỨC THẮNG viết 17:35 ngày 01/10/2018

YĐây là code biểu diễn 1 số dương theo 1 hệ sinh gồm các phần tử dương của mk. (C#)
Dựa vào n là triển khai được bài kia.
Ví dụ input:
N= 4
Hệ sinh: 1 3 5 7
Số cần biểu diễn m=8
Output:
8=81
8=13 + 1*5
…
Vân vân

http://codepad.org/2z6DtlqE

Hello World viết 17:41 ngày 01/10/2018

Code bạn mình không hiểu lắm
mình vẫn chưa học tới.
Bài này mình muốn dùng đệ quy quay lui để giải

NGUYỄN ĐỨC THẮNG viết 17:51 ngày 01/10/2018

Cái của mình dùng quay lui mà.
Ý tưởng:
m là tiền cần biểu diễn
Mảng x chứa hệ sinh (chứa các giá trị tiền có thể đổi)
Mảng tong chứa tổng giá trị khi đã lựa chọn tới bước thứ i,Tức là giả sử lần 1 chọn x1,lần 2 chọn x2…
Thì lần i tổng giá trị tiền đã chọn là x1+x2+… +xi,mục đích mảng này là để đánh giá xem còn chọn được bao nhiêu tiền nữa để đủ.
Mảng appear là số lần xuất hiện của tiền có giá trị x[i] ở kết quả.Tức là số lần đã chọn tiền ấy.

// item “truoc” là để xác định xem lần trước đã chọn tới x mấy rồi,giả sử lần trước chọn tới x2 thì truoc là 2,mục đích là để tránh sự lặp lại ở kết quả (có thể xóa truoc đi test là thấy nếu khó hiểu)

static void SelectItem(int i, int truoc)
{
int j;
// Nếu ở lần chọn trước mà tổng giá trị chọn đã bằng m thì xuất dữ liệu
if (tong[i - 1] == m)
Result();
// Còn không thì tiếp tục chọn
else
{
for (j = truoc; j <= n; j++)
{
// Nếu đồng tiền x[j] định chọn thỏa mãn không vượt quá số lượng tiền đang còn thiếu
if (m - tong[i - 1] - x[j] >= 0)
{
// Chọn x[j] --> tăng số lượng đồng tiền x[j] lên
appear[j]++;
// Cập nhật giá trị mảng tổng
tong[i] = tong[i - 1] + x[j];
// Tiếp tục chọn lần thứ i +1 ,đánh dấu là đang chọn tới đồng tiền x[j] có chỉ số là j
SelectItem(i + 1, j);
// Quay lui lại thì trả appear về giá trị cũ
appear[j]–;
}
}
}