背包笔记

01背包

朴素版01背包

cin >> n >> m;
f[0][0] = 0;
for(int i = 1; i <= n; i ++)
{for(int j = 0; j <= m; j ++){f[i][j] = f[i - 1][j];//第i个物品不选if(j - v[i] >= 0){f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);//选第i个物品}}
}cout << f[n][m];

一维

cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];
//初始化
//一维的要f[0~m]都是0
//如果要恰好背包容量是m的话,要f[0] = 0, f[1~m] = 负无穷
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]);}
}cout << f[m];