动态规划——完全背包问题

完全背包问题相比于01背包问题，不同点在于每个物品可以使用无数次，因此在我们进行dp时，我们的式子也要有相应的改变。

先来看看01背包问题的式子:

f[i][j] = max( f[i - 1][j] , f[ i - 1 ][ j - v[i] ] + w[i] )

由于完全背包中，一个物品可以被选择无限次，因此式子要改成：

f[i][j] = max( f[i - 1][j] , f[i - 1][ j - 1 * v[i] ] + 1 * w[i] , f[i - 1][ j - 2 * v[i] ] + 2 * w[i] … f[i - 1][ j - k * v[i] ] + k * w[i] ) ， 其中k为在体积为j的情况下最多能装 k 件 i 物品

显然，如果按照这个思路进行dp的话，要再建一层循环，循环k次，这会大大增加时间复杂度，使得由原来的 O(n^2) 变成 O(n^3)

我们不妨把上面的式子中的 j 替换成 j - v[i] ，可以得到下列这个式子：

来看例题：

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; int n , m; int f[N] , v[N] , w[N]; int main() { scanf("%d%d" , &n , &m ); for( int i = 1 ; i <= n ; i++ ) cin >> v[i] >> w[i]; 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] ); } } cout << f[m] << endl; }