Cần giúp đỡ bài toán tiêu tiền

#1

Mình đang có 1 bài toán chưa nghĩ ra hướng giải quyết, cần mọi người giúp đỡ gợi ý cho mình với ạ. Bài toán của mình là như vầy:
Mình có 3 loại tiền là VND, đô la, yên (giả sử 3 loại tiền có tỉ giá ngang nhau và không được quy đổi). Các mặt hàng mình muốn mua tuỳ loại mặt hàng có thể thanh toán bằng 1 trong 3 loại tiền hoặc kết hợp các loại tiền với nhau. Ví dụ:

  • Mặt hàng A: VND
  • Mặt hàng B: đô la + yên
  • Mặt hàng C: VND + đô la
  • Mặt hàng D: yên

Bây giờ mình chọn một số mặt hàng rồi, cần kiểm tra xem số tiền mình đang có thì có dùng để mua hết các mặt hàng đã chọn hay không? và nếu có thì mỗi loại tiền mình sẽ mất bao nhiêu. À mà mỗi mặt hàng chỉ được chọn 1 sản phẩm thôi ạ.

số loại tiền kia thật ra lại không phải cố định là 3, mà có thể thay đổi tuỳ dữ liệu thực tế nữa, chỉ biết ít nhất là 1 thôi ạ

#2

Giống bài phân phối nhỉ :smiley:
Ban đầu mỗi thứ là a A, b B và c C.

: a’, b’, c’[i] thuộc {0, 1}
: a, b, c[i] >= 0

với i=1…n, g[i] = a[i]a’[i] + b[i]b’[i] + c[i]c’[i] (nếu a’[i] = 0 tức là không nhận, còn a[i] là số tiền trả, g[i] là giá của món i)

Cho g, a’, b’, c’ là vector hệ số, tìm vector a, b, c sao cho thỏa hệ:

sigma(a[i]) <= a
sigma(b[i]) <= b
sigma(c[i]) <= c
g[i] = a[i] * a’[i] + b[i] * b’[i] + c[i] * c’[i]

3 Likes
#3

đi làm gặp task giống vầy, mình thấy bài toán quen lắm nhưng không biết cách giải :smiley:
số loại tiền kia thật ra lại không phải cố định là 3, mà có thể thay đổi tuỳ dữ liệu thực tế nữa, chỉ biết ít nhất là 1 thôi

#4

Tư duy giải quyết vấn đề như này nhé:

  1. Không cần biết có bao nhiêu loại tiền, chỉ cần biết trong ví đem ra thanh toán có bao nhiêu tiền, và tiền trong túi này chỉ mang 1 mệnh giá duy nhất (ví dụ như chọn ví thanh toán VND thì quy tất cả các loại ví khác về VND rồi cộng tổng lại)
  2. Phải tạo thứ tự ưu tiên cho các ví không phải ví thanh toán (ví dụ xài hết ví VND thì trừ tiếp USD rồi mới xài tới Yen…etc). Cũng có thể tạo cơ chế load-balancing cho ví nếu cần phân bố tiền cho đều =))
  3. Việc nhận biết có đủ tiền mua các mặt hàng sau khi giải quyết (1) + (2) thì là bài toán so sánh 2 số rồi. Cái đó chắc không cần chỉ :slight_smile:
1 Like
#5

nếu cho phép các điều kiện như bạn chỉ ra thì mình đã giải quyết được rồi :smiley:

#6

bạn có thể sử dụng std::map<char,int*> để lưu lại các mặt hàng và loại tiền tương ứng ( int* là mảng 1 chiều 3 phần tử, chẳng hạn B có giá 2 đô la + 3 yên thì lưu {0,2,3} )
khi có map rồi thì tùy vào măt hàng chọn mà tính ra nó cần ? vnd , ? đô la ?yên

1 Like
#7

từng mặt hàng không quy định phải trả bao nhiêu tiền cho từng loại mà chỉ cần biết là có thể kết hợp các loại tiền để trả, tổng các loại tiền bằng giá mặt hàng là được.
và giờ khi mua nhiều loại mặt hàng mình sẽ phải tìm ra từng mặt hàng mỗi loại tiền sẽ trả bao nhiêu là thích hợp để có thể mua được hết các mặt hàng đã chọn

#8

Công ty của bạn được phép giao dịch bằng ngoại hối?

1 Like
#9

hệ thống có nhiều loại tiền ảo, e ví dụ ra tên nó thế thôi ạ :smiley:

#10

Cứ nghĩ cho thanh toán thật :joy:
Vì luật VN hạn chế thanh toán ngoại hối.

Bạn nên đổi sang ví dụ nấu ăn hay hơn: món ăn này cần nhiều gia vị khác nhau, mỗi loại là bao nhiêu gram. Biết ban đầu có các gia vị. Hỏi cách phân chia gia vị như thế nào để có thể nấu nhiều món nhất?

Lúc đó sẽ chuyển sang bài toán phân phối như rogp10 đã nêu.

3 Likes
#11

bài toán @rogp10 quy ra được thì e cũng hiểu cách quy đổi rồi nhưng e học toán cũng hơi kém nên chưa biết hướng giải bài đó, a có tài liệu gì liên quan cho e xin được không ạ? hoặc gợi ý cho e xin hướng giải bài toán đó với ạ (bow)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?