小心下標(biāo)對(duì)應(yīng)不一致帶來(lái)的問(wèn)題。小心。
zero_one_pack(v[i],c[i]) for j = M to c[i] f[j] = max( f[j-c[i]]+v[i] , f[j] )f[0......M] = 0; // 初始化第0行，即一個(gè)物品都沒(méi)有的情形。J一定要包括0.這是關(guān)鍵。for i = 1 to N zero_one_pack(v[i],w[i])下面的代碼i可以從0開(kāi)始，因?yàn)槎S數(shù)組的時(shí)候，i=0開(kāi)始要存儲(chǔ)0個(gè)物品的情形。此時(shí)，不需要。因?yàn)樯弦恍幸呀?jīng)存了。我還是保留了i=1開(kāi)始的情形，小心物品下標(biāo)即可。
class Solution {public: /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ int backPack(int m, vector<int> A) { // write your code here vector<int> f(m+1, 0); int n = A.size(); for(int i = 1; i <= n; ++i){ for(int j = m; j >= A[i-1]; --j){ f[j] = max( f[j], f[j-A[i-1]] + A[i-1] ); } } return f[m]; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
