01背包原理

01背包

每件物品只有一個

樸素演算法

分為兩種情況：①不選第i個物品 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]

? ②選第i個物品 狀態方程可以由 f [ i ? 1 ] [ j ? v ] + w f[i-1][j-v] + w f[i?1][j?v]+w得到

f [ i ? 1 ] [ j ? v ] + w f[i-1][j-v] + w f[i?1][j?v]+w表示前 i ? 1 i - 1 i?1個物品取總體積不超過 j ? v j - v j?v的最大價值加上第 i i i個物品的價值( v , w v,w v,w)分別表示第 i i i個物品的體積和價值

for (int i = 1;i <= n;++i) {
	for (int j = 0;j <= m;++j) {
		f[i][j] = f[i - 1][j];
		if (j >= v[i])f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
	}
}
cout << f[n][m] << endl;

優化成一維

因為對第 i i i維的判斷只用到了 i ? 1 i- 1 i?1維，所以可以用滾動陣列的思想 由樸素的演算法可知 i i i維都是由 i ? 1 i-1 i?1維轉移過來的 如果對 j j j從小到大列舉 計算到 f [ j ] f[j] f[j]時 此時的 f [ j ? v [ i ] ] f[j-v[i]] f[j?v[i]]小于 f [ j ] f[j] f[j]已經被更新到第 i i i維 所以要對 j j j從大到小列舉

for (int i = 1;i <= n;++i) {
	for (int j = m;j >= v[i];--j) {
		f[j] = max(f[j], f[j - v[i]] + w[i]);
	}
}

完全背包

每件物品有無限多個

樸素演算法

f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ? 1 ] [ j ? k ? v [ i ] ] + k ? w [ i ] ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]) f[i][j]=max(f[i][j],f[i?1][j?k?v[i]]+k?w[i])與01背包類似

for (int i = 1;i <= n;++i) {
	for (int j = 0;j <= m;++j) {
		for (int k = 0;v[i] * k <= j;++k) {
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	}
}

優化做法

易知 f [ i , j ] = Max ? ( f [ i ? 1 , j ] , f [ i ? 1 , j ? v ] + w , f [ i ? 1 , j ? 2 v ] + 2 w , f [ i ? 1 , j ? 3 v ] + 3 w , … ) f[i, j]=\operatorname{Max}(f[i-1, j], f[i-1, j-v]+w, f[i-1, j-2 v]+2 w, \quad f[i-1, j-3 v]+3 w, \ldots) f[i,j]=Max(f[i?1,j],f[i?1,j?v]+w,f[i?1,j?2v]+2w,f[i?1,j?3v]+3w,…)

f [ i , j ? v ] = Max ? ( f [ i ? 1 , j ? v ] , f [ i ? 1 , j ? 2 v ] + w , f [ i ? 1 , j ? 3 v ] + 2 w , … ) f[i, j-v]=\operatorname{Max}(\quad\quad\quad f[i-1, j-v], \quad\quad f[i-1, j-2 v]+w, \quad f[i-1, j-3 v]+2 w, \ldots) f[i,j?v]=Max(f[i?1,j?v],f[i?1,j?2v]+w,f[i?1,j?3v]+2w,…)

所以 f [ i , j ] = M a x ( f [ i ? 1 , j ] , f [ i , j ? v ] + w ) f[i,j] = Max(f[i-1,j],f[i,j-v] + w) f[i,j]=Max(f[i?1,j],f[i,j?v]+w)

for (int i = 1;i <= n;++i) {
	for (int j = 0;j <= m;++j) {
		f[i][j] = f[i - 1][j];
		if(j >= v[i])f[i][j] = max(f[i][j],f[i][j -v[i]] + w[i]);
	}
}

優化成一維

在計算 f [ j ] f[j] f[j]時 因為 j ? v [ i ] j - v[i] j?v[i]小于 j j j 所以此時的 f [ j ? v [ i ] ] f[j - v[i]] f[j?v[i]]被更新到了第 i i i維 與原式相符 所以 j j j不需要從大到小列舉

for (int i = 1;i <= n;++i) {
	for (int j = v[i];j >= m;++j) {
		f[j] = max(f[j],f[j -v[i]] + w[i]);
	}
}