Bài toán cái túi

[@viencong]

tóm lại công thức bài này xích ma = Ci * xi + xích ma trước đó, nếu lần đầu thì xích ma trước đó bằng 0 w = b - ai * xi (dùng cho lần đầu tiên tính) các lần còn lại là w = w trước đó - ai * xi g = xích ma + w * (ci + 1) / (ai + 1)

[@diepanhhoang5691]

Nếu đến đoạn xét x4 mà giả sử w khác 0 thì lúc tính g sẽ tính như thế nào ạ? Vì mình ko còn hệ số tiếp theo để nhân vào nữa ạ

[@NQT1709]

em cũng cùng thắc mắc

[@zanmegesuna5798]

Tại sao đến x4 lại dừng và công thức tổng quát của w ở các lần tiếp theo là như nào z ad

[@tanotan3404]

Đề bài là có đến x4 thì mình cần tìm 4 vật thôi b. Bạn xem công thức từ x2 trở đi tương tự b ak

[@zanmegesuna5798]

Mình k thấy tương tự lắm. Ví dụ ở nhánh x2=0 thì W tiếp theo của bạn = W trước đó + a2.x2. Sau đó đến nhánh x3=1 thì W tiếp theo của bạn bằng W trước đó - a3.x3 . Sao cái cộng cái trừ vậy

[@zanmegesuna5798]

Tano Tân rep đi ad

[@tanotan3404]

@@zanmegesuna5798 Nó như nhau bạn ạ. Bạn nghe kĩ đoạn ý mình giải thích đó. Đoạn x2 trên có cộng là mình viết đầy đủ đó bạn. Còn bên dưới x3 nếu viết đầy đủ ra là với x3=1. W(ban đầu là 8) W= 8 - (7.1+0.4 + 1.1)=0 Với x3=0 W=8-(7.1+4.0+1.0)=1 Do bước 2 bạn tính ra w2=8- (7.4+4.0)=1 rồi ý. Thì lấy luôn w2 thày vào tính w3 luôn: w3=w2-(x3.a3)

[@anhle5285]

@@tanotan3404 uk thì do bác viết sai w2=8-7.1+4.0 nên người ta không biết đấy

[@hieune6125]

Sao đến nhánh x3 công thức là b-aixi mà lại làm khác v anh

[@thanhthai18]

11:47 sao tự dưng lại là dấu cộng nhỉ (8-7.1+4.0)... phần túi còn lại thì luôn phải trừ chứ...

[@TaiNguyen-ub1bi]

Nếu đề bài cho x1 , x2 x3 x4 là các số nguyên nhận các giá trị 0 và 1 thì mình ko cần xét nhánh cứ thế cho 2 nhanh là 0 và 1 và giải hả anh ???

[@tanotan3404]

Uk đúng r e. Nếu đề bài cho cụ thể giá trị là 0 1 thì cứ 2 nhánh tính 0 1 thôi

[@tanotan3404]

Chỉ cần xem nếu có nhánh 0 thôi thì ko phải tính nhánh 1 đâu

[@trinhcuong9188]

Anh cho em hỏi là: 1. Nếu ở bước sắp xếp như ban đầu mà mình có 2 cái tỉ số ci/ai bằng nhau thì xếp cái nào trước cũng được hả anh? 2.Nếu bước tính nhánh mình được 3 nhánh, nhưng đề phải yêu cầu chỉ lấy 2 nhánh thì mình chọn lấy 2 nhánh trong 3 nhánh như thế nào ạ?

[@tanotan3404]

1. Uk bằng nhau thì giữ hay đổi đều đc cả, tại như nhau e. 2. Đề cho 2 nhánh thì dù tính ra bao nhiêu nhánh vẫn chỉ lấy 2 nhánh 0 và 1 (Nhánh lấy từ 0 trở lên nhé e)

[@phatthanh4986]

anh cho e hỏi, sao công thức xích ma của anh ghi ra là xích ma = Ci.Xi, mà trong quá trình làm ví dụ thì lại cộng thêm xích ma trước đó nữa , v công thức tổng quát phải là xíchma = xíchma(trước đó) + Ci.Xi mới đúng chứ anh

[@hoango6382]

Cho mình hỏi là ở ô đầu tiên mình ghi f ngang bằng + vô cùng được kh tại trong sách mình thấy ghi vậy. với lại lúc nào mình cũng sắp xếp giảm dần hay tuỳ đề bài mình sắp giảm hoặc tăng vậy bạn ?

[@tanotan3404]

Cô giáo mình thì bảo dạng này là - vô cùng. CÒn sách mình đọc thì cái nào cũng + vô cùng hết. Dạng bài này là mình đang đi tìm max nên luôn xếp giảm bạn ạ(Có cái bài du lịch thì là tìm min)

[@tanminhlai4011]

a cho e hỏi là đến x4 là ci/ai=0,25 đáng ra chỉ lấy 0 mà đề bài cho xj={0;1} thì vẫn lấy 2 nhánh đúng k ạ

[@tanotan3404]

Cái 0,1 kia thì là số nhánh max đối với trường hợp chia ra được số nhánh lớn hơn 2 thì mình lấy 2 nhánh thôi.. Chứ nếu mà chia ra chỉ có 1 nhánh thì chỉ làm 1 nhánh 0 thôi e!

[@tanminhlai4011]

Tano Tân e cảm ơn

[@HienPham-hk7xb]

cái này làm theo phương pháp nhánh cận đúng không ạ?

[@tanotan3404]

Hiển Phạm đúng r b

[@minhdungle5854]

tại sao f lại tiến tới âm vô cùng vậy ạ ???

[@phonghong3844]

nếu không sắp xếp giảm thì e làm vẫn ra đúng mà a?

[@tanotan3404]

Không sắp xếp có trường hợp vẫn đúng e. Nhưng nhiều trường hợp sai lắm e nhé. Em thử làm bài của a trong video mà không sắp xếp mà xem

[@phonghong3844]

@@tanotan3404a cho e hỏi ạ.Xét cái cuối cùng x4 thì ko có giá trị g chứ a. Vì g=~+w.c[i+1]/a[i+1] mà đã hết đồ vật r thì sao tính dc tỉ số c/a được ạ

[@phonghong3844]

@@tanotan3404 e làm ko sắp xếp với đề của a thì vẫn ra đúng mà a

[@tanotan3404]

@@phonghong3844 Tính giá trị cuối là x4 thì giá trị sau từ x5 là 0 em nhé. Còn ko sắp xếp là sai đó em. Có trường hợp nó vẫn đúng. Ví dụ e giải đề sau mà ko sắp xếp là sai này: 10x1 + 3x2+5x3+6x4->max; 5x1+ 2x2 + 3x3 + 4x4

[@cuongvu9063]

a cho e hỏi là nếu đến x4 mà w không = 0 thì g tính kiểu gì ạ

[@tanotan3404]

cuong vu : không bằng 0 thì vẫn kết luận bìn thường e ạ. Ko nhất thiết phải bằng 0 nhé. Nó max là max ở cái biểu thức thứ nhất. Ko phải max ở biểu thức thứ 2. E cộng thử mà xem. Phương án chọn của cái mà e tính ra khác 0 ý nó là max

[@cuongvu9063]

-ý e là tính g của x4 ý ạ tại vì nếu tính x3 thì g=0~ + W*(c4/a4) còn x4 thì lấy c mấy và a mấy ạ -tại sao w của x2 thì là cộng thêm mà đến w của x3 thì lại là trừ ạ mấy hôm nữa e thi mà vẫn còn chỗ thắc mắc :((

[@tanotan3404]

nếu x nào ko nhìn thấy thì lấy là 0 e nhé. => xét x4 thì hệ số x5 không có sẽ là 0/0 Còn cái w ở video ý.. X2 là anh viết đầy đủ.. Cả hệ số x2, và x1.. X3 công thức vẫn vậy.. Nhưng a lấy luôn kết quả từ x2 (=1 ý) nên a trừ đi x3 thôi.. Nên nó mới như vậy đó.. Còn đâu e cứ thay công thức bình thường ý. nó như nhau e nhé :))) Cố lên sắp xong rồi :))

[@danhkhuongnguyen9879]

sai, nếu sắp xếp mà ko sắp xếp chỉ số của x thì sẽ thay đổi luôn đề bài

[@tanotan3404]

Mình bảo sắp xếp cả hệ số trên dưới cùng một lúc mà

[@danhkhuongnguyen9879]

@@tanotan3404 sau khi tìm ra XOPT bạn phải đảo lại theo thứ tự của đề bài thành 1,0,0,1. Bạn thử thay đáp án của bạn vào đề bài đi, tổng khối lượng là 11>8.

[@tanotan3404]

Ak. Bạn thay vào phương trình sau khi đổi chõ chứ. Giờ đề bài là phương trình mới r mà.

[@danhkhuongnguyen9879]

@@tanotan3404 thì bạn kết luận theo đề bài mới nên mình mới nói sai

[@Phom181]

cho mình hỏi nếu số nhánh đầu là 3 nhánh thì lấy x1=2,x1=1,x1=0 ạ

[@tanotan3404]

kiên nguyễn số nhánh bạn chia ra là 3 thì lấy 0 1 2 3 nhé b. B xem đầu bài có nói lấy tối đa mấy nhánh không nhé.

[@Phom181]

7x1 + 3x2 + 2x3 + x4 --> max 5x1 + 3x2 + 6x3 + 4x4

[@tanotan3404]

kiên nguyễn thuộc (0,1) thì max là 2 nhánh thôi b. Dù chia ra có lớn hơn 1 thì vẫn lấy 0,1

[@lookinglook8480]

tại sao trong giáo trình của e không có cái sắp xếp vậy a. không sắp xếp có đk ko

[@tanotan3404]

Do trong giáo trình nó đã là đúng rồi. Còn e xem thuật toán thì sẽ thấy đoạn sắp xếp. Nếu không giảm dần thì phải sắp xếp e ạ. Ko nó sẽ ra sai

[@vantuongma4498]

Anh ơi. Tại sao phải sắp xếp lại thứ tự ạ?

[@tanotan3404]

Ko sắp xếp lại thì chọn nó ko tối ưu e ạ. E thử giải lại bài này mà ko sắp xếp. Kết quả nó khác mà ko tối ưu bằng đâu e

[@vantuongma4498]

@@tanotan3404 vâng. Tại hôm nay em bị vướng khi mà g ở hai nhánh bằng nhau em không biết đi theo nhánh nào. Có phải đi theo nhánh có sigma lớn hơn không ạ? Mà khi duyệt đến x cuối thì g luôn bằng sigma à anh?

[@banao6613]

cộng w vào là sai, chưa đổi lại vị trí ==> sai++

[@bbb-bj9rt]

em tưởng phải trả lại thứ tự X như ban đầu chứ , kết luận như v là chưa đúng rồi anh

[@phamhien4118]

hướng dẫn bài atm quay lui đi ạ

[@hoanganhnguyen1754]

giả sử đề :5x1 + 8x2 + x3 + x4 => max ; 4x1 + 7x2 + x3+ x4

[@nhom3lop7a80]

anh ơi dạy bài atm quay lui đi ạ

[@namle-vh5ip]

cho em hỏi nếu ở x4 =1 hay khác không thì c(i+1)/ a(i+1) bằng gì vậy anh nghĩ là không có x5 để mình thay vào á

[@phongnv204]

Anh dạy hay, ngọng dễ thương quá

[@tanotan3404]

Phong Nguyễn Văn Ngọng chỗ nào e :)))

[@phongnv204]

Tano Tân nào -> lào Này -> lày 😬😄😄

[@phongnv204]

anh có làm trường hợp nào lúc cuối w khác 0 không ạ?? em có đề này anh xem với: 7x1 + 3x2 + 2x3 + x4 --> max 5x1 + 3x2 + 6x3 + 4x4

[@tanotan3404]

Phong Nguyễn Văn ak n và l a nói bthg đc ... Nhưg ở quê toàn nói l thôi nên quen r :))) Có e nhé. Mục đích chọn là e cộng hệ số hàng trên nó max là đc. W còn kệ nó. Chọn x1 vs x2 thì hàng trên giá trị nó max r e ạ.

[@annnguyen4789]

cho mình hỏi nếu mà j=1,5 thì cũng làm 2 nhánh hả hay thế nào

[@tanotan3404]

Không bạn. Số nhánh thì do từng bước mình tính bạn ạ. Trong video mình cũng nói cách tính rồi đó. Không phải là lúc nào cũng hai nhánh đâu. Nó phụ thuộc vào kết quả chia ở từng bước Còn nếu đề bài cho chỉ nhận 0,1 thì mới là lúc nào cũng 2 nhánh bạn ạ

[@ldhvlogs3581]

Cảm ơn anh

[@tanotan3404]

Chúc e học tốt!

[@tanduyle4575]

chữ đẹp quá,mình thật gato vs b

[@tanotan3404]

Tân Lê :))) Cảm ơn b :))

[@thanhhuyen3219]

A quay này bọn e k nhìn đc hết ý 😊

[@tanotan3404]

Huyen Hoang Thi a mải nhìn giấy haha

[@thanhhuyen3219]

Nhánh thứ 2 x2=0 , w=1-4.0 chứ k phải là 1+4.0 đúng k a

[@hMuzik99]

a học uneti ạ

[@tanotan3404]

Uk đúng rồi em