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

简介: 算法模板:动态规划之完全背包

前言


唤我沈七就好啦。


往期系列文章

动态规划之01背包


完全背包


有 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/


相关文章
|
6天前
|
存储 算法
数据结构与算法之动态规划--旷工问题
数据结构与算法之动态规划--旷工问题
14 1
|
7天前
|
机器学习/深度学习 存储 算法
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
LeetCode题目 90:五种算法 回溯\迭代\位掩码\字典树\动态规划实现 子集ll
|
8天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
8天前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
|
8天前
|
存储 SQL 算法
解锁动态规划:从斐波那契到高效算法
解锁动态规划:从斐波那契到高效算法
|
10天前
|
存储 算法
动态规划与搜索算法
动态规划与搜索算法
12 0
|
14天前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
14天前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
14天前
|
机器学习/深度学习 算法 测试技术
【算法优选】 动态规划之子数组、子串系列——壹
【算法优选】 动态规划之子数组、子串系列——壹
|
14天前
|
算法
【算法优选】 动态规划之简单多状态dp问题——贰
【算法优选】 动态规划之简单多状态dp问题——贰