Tìm giải thuật tốt hơn cho bài toán này

#1

Bài toán mình đang có tóm tắt như thế này:
Giả sử muốn tạo ra một chiếc xe cần có tối thiểu 5 loại linh kiện chính. Mỗi loại linh kiện chia ra làm 2 loại, loại tốt made in japan - đơn giá 1, loại thường made in china - đơn giá 2
Câu hỏi:
Một người có một số tiền nhất định, muốn lắp 1 chiếc xe nên cần mua 5 loại linh kiện. Tính toán xem số tiền của người đó có đủ để mua 5 loại linh kiện với đơn giá 1 hết hay chỉ đủ mua 5 loại với đơn giá 2 hết. Nếu số tiền trong khoảng giữa (dư sức mua hết 5 loại với đơn giá 2 nhưng ko đủ mua 5 loại với đơn giá 1. Tìm một phương án gồm những linh kiện theo đơn giá 1 và linh kiện theo đơn giá 2 để mua.

Giải thuật mình lập ra như sau:
all1 = tổng 5 LK tốt với đơn giá 1
all2 = tổng 5 LK thường với đơn giá 2
money = số tiền người đó có

if (money > all2 && money  < all1)
{
        //bắt đầu là mua hết 5 loại Linh kiện (LK) thường 
        int sum = all2;
        //xong xét trong 5 loại LK đó có thay đc cái nào thành loại tốt ko
        for(int i=1; i<=5;i++)//cần mua 5 LK nên có 5 vòng lặp, bắt đầu từ LK 1 
        {
                if (sum - (LK [i] đơn giá 2) + (LK [i] đơn giá 1) <= money)
                {
                     Sum -= LK[i] đơn giá 2;
                     Sum += LK[i]đơn giá 1;
                     //code thêm để biết LK thứ i có thể thay = loại tốt
                }
                else
                      continue;//ko break ở đây vì biết đâu với số tiền còn lại ko đủ để thay LK thứ i = loại tốt 
                      nhưng đủ để mua LK thứ i+1 loại tốt.
          }
}

Có cảm giác giải thuật này vẫn chưa tốt lắm. Ai có giải thuật nào tốt hơn xin thỉnh giáo.

1 Like
#2

do chỉ có 5 linh kiện và mỗi linh kiện chỉ có 2 lựa chọn, tức là chỉ có 25 = 32 trường hợp, khá ít nên bạn có thể tính trước giá tiền của từng trường hợp, rồi sắp xếp nó lại theo giá tăng dần, rồi tìm kiếm nhị phân xem số tiền nằm trong khoảng nào rồi lấy cận dưới là được.

ví dụ có 2 linh kiện, mỗi linh kiện có 2 lựa chọn, linh kiện thứ nhất giá 5-8, lk thứ hai giá 10-19
giá tiền của lựa chọn thứ 0 (00) (0 = đồ china, 1 = đồ japan) = 5+10 = 15
giá tiền của lựa chọn thứ 1 (01) = 5+19 = 24
giá tiền của lựa chọn thứ 2 (10) = 8+10 = 18
giá tiền của lựa chọn thứ 3 (11) = 8+19 = 27
sắp xếp theo giá tăng dần:
{(00,15), (10, 18), (01, 24), (11,27)}
số tiền của người đó ví dụ là 20. Tìm kiếm nhị phân thấy 20 nằm trong khoảng [18,24), lấy giá trị 18 tức là lựa chọn thứ 2 (10), hay lk thứ 1 là đồ japan, lk thứ 2 là đồ china cho người ta.

#3

Cảm ơn bạn tntxtnt trả lời quá nhanh! Mình hỏi thêm là nếu câu sau tăng từ 5 lên thành 10 linh kiện, tức là 1024 trường hợp, cách của bạn vẫn ok hay phải tìm cách khác tốt hơn.

#4

1024 cũng ko quá nhiều, xài vô tư

với trường hợp có nhiều cấu hình trùng giá thì bạn có thể chuyển sang std::map<int, std::vector<int>> mà xài.

Ví dụ thay vì sắp xếp mảng {(0,15), (1, 24), (2, 24), (3,27)} thì bạn xài std::map:

{
  15 => [0],
  24 => [1,2],
  27 => [3]
}

ví dụ số tiền là 25 thì bạn xài std::map::lower_bound để tìm key lớn nhất mà bé hơn hoặc bằng 25, ở đây nó sẽ trả về 24 => [1,2], lấy ra [1,2] rồi chọn 1 trong số đó là được, hoặc bày ra các cách để user họ chọn.

đúng ra với số tiền 25 thì họ vẫn có thể chọn cấu hình 0 với giá 15. Sao ép họ mua cấu hình giá 24 được :joy:

#6

This post was flagged by the community and is temporarily hidden.

#7

Mình cũng đang dính một bài tương tự, bạn hướng dẫn mình cách code giải thuật của bạn đuợc không, thx bạn nhiều

#8

xài map<int,vector<int>> để chứa giá từng cấu hình, rồi tìm cận dưới thôi.

vd ở đây có 5 linh kiện, mỗi linh kiện có 2 loại giá

đầu tiên là tạo bảng giá: mảng int 5x2. std::vector<std::vector<int>> priceTable(5, std::vector<int>(2)); rồi lần lượt gán priceTable[i][j] với giá linh kiện thứ i (i=0…4) loại j (j=0,1) tương ứng.

tiếp theo là liệt kê từng cấu hình và giá của nó. Ví dụ ở đây có 5 linh kiện, mỗi linh kiện có 2 loại giá thì có tổng cộng 32 cấu hình, cho int config chạy từ 0 tới 31:
for (int config = 0; config < 32; ++config)
biểu diễn hệ nhị phân của giá trị config cho biết giá của từng loại linh kiện. Ví dụ với config = 5 thì 5 = (00101)2, tức là

Linh kiện thứ (i): 4 3 2 1 0
Loại (j):          0 0 1 0 1

linh kiện thứ 0 là loại 1, lk thứ 2 là loại 0, v.v… Có i, j rồi thì tra lại trong bảng priceTable là tính được tổng tiền int totalPrice của int config tương ứng.

liệt kê được rồi thì việc tiếp theo là bỏ vào 1 ctdl phù hợp. Ở đây mình chọn cho vào 1 binary tree map int totalPrice tới các int config tương ứng. Gọi ctdl này là std::map<int, std::vector<int>> priceConfigsMap; Bước này chỉ việc gọi priceConfigsMap[totalPrice].push_back(config) là được.

cuối cùng là tìm cận dưới cho int payAmount:

auto it = priceConfigsMap.upper_bound(payAmount);
if (it == priceConfigsMap.begin())
{
    //ko đủ tiền cho cấu hình thấp nhất
}
else
{
    auto configs = (--it)->second; //mảng chứa các config có giá gần với payAmount nhất
    //nếu configs.size() == 1 thì chọn config tương ứng, còn size > 1 thì liệt kê ra các cấu hình
}

edit: upper_bound tiện hơn :stuck_out_tongue:

#9

Bạn còn cách nào khác không, mình chỉ mới học được loop, array, pointer, struct mấy cái căn bản trong c++ thôi, map, vector gì gì mình chưa học nên không áp dụng được

#10

vậy thay vì bỏ vào cái map thì bạn chạy kiểm tra thử từng cấu hình rồi lưu cấu hình có tổng số tiền gần với số tiền hiện tại nhất.

#11

Cách này post đầu bạn có nhắc tới, cũng là cái cách mình đang không biết cách code, mình code tựa thế này:
arrSP[7] = {0,1,2,3,4,5,6} // Mảng lưu số SP
arrPrice1[7] = {10,5,6,7,3,6,4,9,11} //Mảng lưu giá loại 1 tương ứng
arrPrice2[7] = {9,2,3,5,2,5,3,3,9)// giá loại 2
Có 7 sản phẩm, viết code thế nào để nó pick 5 sản phẩm có tổng giá gần = số tiền mua. P/s: Mình có đang đi sai hướng không nhỉ

#12

This post was flagged by the community and is temporarily hidden.

#13

có lẽ phải duyệt trâu hết 2^7 trường hợp thôi

#14

sắp xếp thì mới học loop array pointer gì thôi thì có sắp xếp cũng O(n^2), chậm rì, nên thôi duyệt trâu luôn cho rồi. Với lại sắp xếp cũng có thể gặp trường hợp này:
5 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9
chẳng hạn. Nếu người mua có tiền = 8 thì tìm kiếm nhị phân chỉ ra được 1 giá trị, trong khi có thể cần đếm vd ở đây là 14 cấu hình có cùng giá tiền 8 để người mua có thể lựa chọn 1 trong 14 cấu hình này. Xài map thì gom chung tụi nó lại được :joy:

#15

This post was flagged by the community and is temporarily hidden.

#16

Chỉ mình code :scream:, mò google nửa tuần rồi không ra cách code. Ai có link bài tương tự đã có người giải thì cho mình xin luôn.

#17

tạo 1 cái struct gồm loại linh kiện và giá của nó. Sau đó tạo 2 cái mảng hay vector để chứa dữ liệu cho linh kiện tốt và xấu. Tiến hành sort theo giá cả, dùng qsort cho tối ưu. 2 bước kiểm tra đầu thì đơn giản mình kiểm tra thằng lưng chừng. Dùng 1 vòng lặp, chọn 1 cái rẽ nhất của cái xấu với 4 cái cái rẽ nhất loại tốt nhưng khác loại với cái đã chọn, kiểm tra điều kiện nếu thõa thoát nếu không chọn 2 cái rẽ nhất loại xấu và 3 cái rẽ nhất loại tốt và kiểm tra. cứ như vậy sẽ ra đc kết quả. Mình nhớ k nhầm thì đây là thuật toán tham lam ^^

#18

cảm ơn bạn, mình biết là dùng giải thuật tham lam, tại hôm đó vừa học giải thuật này xong thì bà cô đưa bài này về làm thì chắc chắn là chỉ có dùng tham lam. Mà mình kẹt ở chỗ là nếu chỉ có 1 loại giá tiền thì mình làm đc, còn đây tới 2 loại giá nghĩ ko ra cách code.

#19

mình không hiểu ý bạn cho lắm, giải thuật mình đã nói ở trên, nếu bạn hiểu có thể hoàn toàn code đc vì nó rất đơn giản mà?

#20

Ở chỗ này đây, vd cần 5 sp và cửa hàng cũng chỉ bán đúng 5 sp thì ok. kiểm tra 2^5 trường hợp như cách bạn nói. SP 1 2 3 4 5. Nhưng nếu cần 5 sp nhưng cửa hàng có thể có tới 10 sp thì phải kiểm tra SP 1 2 3 4 5 rồi 2 3 4 5 6, 1 3 4 5 6,… thì code thế nào để trộn giá loại 1 loại 2 rồi còn thay đổi SP từ 1 đến 10 sao cho ko trùng.

#21

cái đề bạn nói mình nghĩ có vấn đề rồi, làm chiếc xe chỉ cần 5 linh kiện, mà cửa hàng bán 10 linh kiện là sao? Mình chỉ mua cái cần mua thôi chứ, hay là cùng loại linh kiện nhưng khác giá? Nếu vậy thì mình vẫn làm y như cũ, chỉ là khi chọn loại linh kiện mình cần loại bỏ những loại linh kiện đã chọn rồi mà thôi, giá của nó vẫn phải luôn là rẽ nhất ^^ Cái thứ 2 nữa là hình như bạn nhầm, ở đây thuật toán mình đưa ra là O(n) tức duyệt từ 1 đến n linh kiện xấu, chứ không phải 2^n như bạn nghĩ.

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