完全背包问题思路上和代码都和01背包问题很相似,可以对照记忆,01背包的题解如下:
https://www.acwing.com/solution/acwing/content/10449/
版本一:这是朴素版本的,时间复杂度$O(nm^2)$,TLE了
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[N][N], v[N], w[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
for(int k = 0; k * v[i] <= j; k ++ )
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
cout << dp[n][m] << endl;
}
版本二:这个就是讲数据输入在枚举状态的时候进行。和版本1没有本质区别
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[N][N], v[N], w[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for(int j = 0; j <= m; j ++ )
for(int k = 0; k * v <= j; k ++ )
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v] + k * w);
}
cout << dp[n][m] << endl;
}
版本3:这个就是把上面版本的第三重循环优化掉,优化的原理就是:
dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2 * v] + w, dp[i - 1][j - 3 * v] + 2 * w, .....);
而我们需要的dp[i][j]的状态表示是:
dp[i][j]= max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w, dp[i - 1][j - 3 * v] + 3 * w);
将每一项一一比对,我们可以得到下列状态表示:
dp[i][j] = max(dp[i - 1][j], dp[i][j - v] +w);
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[N][N], v[N], w[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for(int j = 0; j <= m; j ++ ){
dp[i][j] = dp[i - 1][j];
if(j >= v)
dp[i][j] = max(dp[i - 1][j], dp[i][j - v] + w);
}
}
cout << dp[n][m] << endl;
}
版本4:滚动数组优化,就是将第一个维度直接&1,那么数据就会保存在dp[0][x]和dp[1][x]中。只要用到dp[2][N]这么大的数组就足够了。
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[2][N], v[N], w[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for(int j = 0; j <= m; j ++ ){
dp[i & 1][j] = dp[(i - 1) & 1][j];
if(j >= v)
dp[i & 1][j] = max(dp[i & 1][j], dp[i & 1][j - v] + w);
}
}
cout << dp[n & 1][m] << endl;
}
版本5:这是课上讲的优化版本,对代码进行等价变形。对照01背包的代码,就是将第二个循环从小到大进行枚举即可。
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int dp[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
int v, w;
cin >> v >> w;
for(int j = v; j <= m; j ++ ){
dp[j] = max(dp[j], dp[j - v] + w);
}
}
cout << dp[m] << endl;
}
写的太好了,可惜我点不了赞
$很棒hh$
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);版本一的转移方程为什么不是这样dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * v[i]] + k * w[i]);
qiang
版本三是不是写错了啊,,说明里给出的状态方程是dp[i][j] = max(dp[i - 1][j], dp[i][j - v] +w),,但代码里面是dp[i][j] = max(dp[i][j], dp[i][j - v] + w);
因为上面有一行dp[i][j] = dp[i - 1][j], 所以就直接和dp[i][j]进行比较了~
dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w)
为啥第二个dp[i][j]不是dp[i-1][j]呢?
你可以试一试, 应该是都能通过的, 只不过在之前dp[i][j] = dp[i - 1][j]了, 就没有必要再写 i - 1了
好像不可以
可以的
因为 最后把dp[i-1][j] 当作了 k为0的情况
在n3的情况下也就是最暴力的那一版代码里面,用dp[i-1][j]去更新会有错误答案,我也没搞懂为什么。求解。
具体的式子给一下
就是楼主的版本一的代码,更新时用dp[i-1][j]而不用dp[i][j]。
你看上面是可以比了,因为k==0时候就是dp[i-1][j],但是你最起码先跟自己比
看到了,多谢!
版本三由呢个原理得出来的公式 是怎么对比出来的啊 大佬!!!求解答
dp[i][j - v] = max(dp[i - 1][j - v], dp[i - 1][j - 2 * v] + w, dp[i - 1][j - 3 * v] + 2 * w, .....);
dp[i][j]= max(dp[i - 1][j], dp[i - 1][j - v] + w, dp[i - 1][j - 2 * v] + 2 * w, dp[i - 1][j - 3 * v] + 3 * w);
可以看到第二个公式里面的所有项再+一个w就和第一个公式里面的从第二项开始的每一项都是完全相同的了, 再加上第一个公式的第一项,max(dp[i - 1][j], dp[i][j - v] + w)就有第一个公式的所有项了.
啊啊啊啊太感谢了!!!!终于迷过来了 ,太感谢了!!!
dp[i][j] = max(dp[i][j], dp[i - 1][j - v] + w)
为啥第二个dp[i][j]不是dp[i-1][j]呢?
应该是第一个公式里面所有项+w就和第二个公式里面第二项开始的每一项都是相同的了
版本5的那个v[N], w[N]可以不要了
是的 忘记改了
为什么滚动数组这次是从小到大了,而01的话要从大到小 有懂了大佬解释下嘛
你可以对比一下公式,实际上01背包从大到小就是使用上一行的状态更新。然后完全背包是使用当前行的状态更新。
非常感谢!按这思路我回去打印了步骤,如果01背包不倒着来,就相当于本来只能用1次的物品可以多次使用了。
对的,就是完全背包了。,
很全, 牛
课是指的什么课?
acwing的算法基础课
点赞,在你这里看懂了版本3!