算法模板：动态规划之完全背包【沈七】

文档中心

算法模板：动态规划之完全背包

前言
完全背包
- 递推优化
- 降维优化
- - 奶牛的干草
- 综合应用
- - 神奇的四次方数
完结散花
参考文献

前言

唤我沈七就好啦。

往期系列文章
动态规划之01背包

完全背包

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

完全背包与01背包的区别就是每种物品都有无限件可用。

#includeusing 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])

最终代码

#includeusing 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数组需要初始化成一个很大的数。

坑点：本题要求是在到达重量要求后，所需价值最小，
由于每个公司的价格不同，所以并不是恰好达到重量后花费最小。
所以需要再遍历一遍所有达到要求重量要求的方案，找到其中的最小值。

#includeusing 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=5⁴⁺³4,则n=2。

每个数可以用多次。

题解部分：

每个数可以用多次。

这句话是我加的，我用01背包做了半天。。。

1.因为要求是最小值，所以 d p数组应该初始化为正无穷。

2.为了使d p数组有意义需要让d p[0] = 0

#includeusing 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/

算法模板：动态规划之完全背包【沈七】