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