前言
唤我沈七就好啦。
往期系列文章
完全背包
有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
完全背包与01背包的区别就是每种物品都有无限件可用。
#include<iostream> using namespace std; const int N = 1010; int f[N][N]; int v[N],w[N]; int main() { int n,m; 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++) f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); } cout<<f[n][m]<<endl; }
递推优化
我们列举一下更新次序的内部关系：
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w …)
f[i , j-v] = max( f[i-1,j-v] , f[i-1,j-2*v] + w …)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i][j-v]+w , f[i-1][j])
降维优化
有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：
f[j] = max(f[j-v]+w , f[j])
最终代码
#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int dp[N]; int v[N],w[N]; int main() { int n,m; 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 = v[i];j <= m ; j ++) //完全背包不需要改变遍历顺序 //这也是优化后完全背包与01背包的区别 { dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } cout<<dp[m]; return 0; }
奶牛的干草
约翰的干草库存已经告罄，他打算为奶牛们采购 H(1≤H≤50000) 磅干草。
他知道 N(1≤N≤100) 个干草公司，现在用 1 到 N 给它们编号。第 i 公司卖的干草包重量为 Pi(1≤Pi≤5,000) 磅，需要的开销为 Ci(1≤Ci≤5,000)美元。每个干草公司的货源都十分充足， 可以卖出无限多的干草包。
帮助约翰找到最小的开销来满足需要，即采购到至少 H 磅干草。
分析：本题是要找最小值，所以dp数组需要初始化成一个很大的数。
坑点：本题要求是在到达重量要求后，所需价值最小，
由于每个公司的价格不同，所以并不是恰好达到重量后花费最小。
所以需要再遍历一遍所有达到要求重量要求的方案，找到其中的最小值。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long dp[N],ans=9999999; long long v[N],w[N],m,n; int main() { cin>>n>>m; for(int i = 1 ; i <= m +5000; i ++) dp[i]=1e9; 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+5000;j ++) { dp[j]=min(dp[j],dp[j-v[i]]+w[i]); } for(int i = m ; i <= m+5000; i ++ ) ans=min(dp[i],ans); cout<<ans; return 0; }
综合应用
神奇的四次方数
将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=54+34,则n=2。
每个数可以用多次。
706
2
题解部分：
每个数可以用多次。
这句话是我加的，我用01背包做了半天。。。
1.因为要求是最小值，所以 d p数组应该初始化为正无穷。
2.为了使d p数组有意义 需要让d p[0] = 0
#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; int dp[N],n; int main() { cin>>n; memset(dp,0x3f,sizeof(dp)); dp[0]=0; for(int i = 1; i <= 20 ; i ++) for(int j =i*i*i*i;j <= n ; j ++) { dp[j]=min(dp[j],dp[j-i*i*i*i]+1); } cout<<dp[n]; return 0; }
完结散花
ok以上就是对 动态规划之完全背包 的全部讲解啦，很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
参考文献
https://www.acwing.com/activity/content/19/
