關(guān)于動(dòng)態(tài)規(guī)劃算法01背包原理，dp動(dòng)態(tài)規(guī)劃中的背包問(wèn)題01這個(gè)問(wèn)題很多朋友還不知道，今天小六來(lái)為大家解答以上的問(wèn)題，現(xiàn)在讓我們一起來(lái)看看吧！
1、(1)將二維數(shù)組轉(zhuǎn)化為一維數(shù)組之后，f[v]表示v的容量最多裝多大價(jià)值。
2、如果順序枚舉的話，每種物品可能多次使用。
3、例如某個(gè)物品重量為5，價(jià)值為10，那么就會(huì)用f[0]去更新f[5]，用f[5]去更新f[10]，最后出現(xiàn)f[0]=0，f[5]=10，f[10]=20的情況。
4、而這是01背包，要求每種物品只能用一次。
5、逆序枚舉時(shí)，是在f[5]被f[0]更新之前，就用f[5]更新f[10]，這樣就可以保證用一次。
6、(2)首先要搞明白f[i][v]的定義:用前i種物品恰好裝滿一個(gè)容量為v的背包，最大價(jià)值是多少。
7、這句話的意思就是說(shuō)，費(fèi)用總和為v的狀態(tài)可能沒有意義。
8、譬如說(shuō)所有物品加在一起的重量都不到v，那么f[N][V]必然沒有意義了。
9、只能去找f[N][0..V]中的最大值來(lái)輸出。
10、但是如果我們改變一下f[i][v]的定義:用前i種物品，在總重不超過(guò)v的情況下，最大價(jià)值是多少。
11、就可以直接輸出f[N][V]了，這樣只需要改變一下轉(zhuǎn)移方程，加上一項(xiàng)f[i][v-1]。
12、還有問(wèn)題請(qǐng)追問(wèn)。
本文分享完畢，希望對(duì)大家有所幫助。
標(biāo)簽：
免責(zé)聲明：本文由用戶上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！