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

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ó 2⁵ = 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.

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.

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

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

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

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)₂, 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

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

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.

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ỉ

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

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

Các giaỉ thuật : Tính gía dựa trên cấu hình. Xắp xếp cấu trúc, Tìm kiếm nhị phân.

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

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

Chỉ mình code , 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.

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 ^^

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.

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à?

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.

Ở 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.

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ĩ.

giải thuật tham lam, mỗi sp có 2 giá tức 2^1 cách chọn vật phẩm. Có n vật phẩm thì ko phải sẽ có 2^n cách chọn sao, tính hết các trường hợp đó rồi giá nào gần với giá tiền bỏ ra nhất thì chọn, ko phải giá rẻ nhất thì chọn.
Mình đang kẹt chỗ loại bỏ các sp đã chọn rồi ra ko tính nữa.