浅谈完全背包问题-阿里云开发者社区

浅谈完全背包问题

2024-10-09 9

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 浅谈完全背包问题

完全背包问题呢，见名知意，就是所谓的物品无限多，选也选不完的那种，是多重背包的promax版本。完全背包问题是背包问题的一种变体，与0/1背包问题有所不同。在完全背包问题中，每种物品的数量是无限的，可以选择任意数量的某一种物品放入背包中。问题的描述如下：

给定一个背包容量为m，有n种物品，每种物品有重量v[i]和价值w[i]，且数量无限。目标是选择物品放入背包，使得它们的总重量不超过背包容量，并且总价值最大。

与0/1背包问题相比，完全背包问题的状态转移方程有所不同，因为每种物品可以选择多次。

解决完全背包问题的方法与0/1背包问题类似，可以使用动态规划、贪心算法等。常见的动态规划方法包括自底向上的迭代和自顶向下的递归+记忆化搜索。

既然是promax版本，那还是离不开01背包啊，既然我可以无限选，那就可以选到知道背包装不下为止，就是m/v[i]。

例题就用acwing上的完全背包问题：3. 完全背包问题 - AcWing题库

朴素版——枚举k

最先想到的就是简单的枚举k了吧，把完全背包转换成多重背包，每个物品最多枚举到m/v[i]，相当于每个物品的个数确定了。

#include<iostream>
using namespace std;
int dp[1005],a[1005];
int n,m;
int v[1005],w[1005];
int main(){
  cin>>m>>n;
  for(int i=1;i<=n;i++){
    cin>>v[i]>>w[i];
  }
  for(int i=1;i<=n;i++){
    for(int j=m;j>=1;j--){
      for(int k=0;k<=j/v[i];k++){
        if(j>=k*v[i]){
          dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
        }
      }
    }
  }
  cout<<dp[m]<<endl;
  return 0;
}

这里为了好理解写了朴素版本的多重背包，可以二进制优化和单调队列优化，具体可以看一下我上

一篇博客写的

这个枚举k肯定过不了，时间复杂度太大，考虑优化

进阶版——dp正推（一维滚动数组）

#include<iostream>
using namespace std;
int dp[1005];//dp[i]表示背包容量为i是最大价值
int n,m;//n个物品m背包容量
int v[1005],w[1005];
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=v[i];j<=m;j++){//这里从v[i]到m，保证了能选1——m/v[i]（最多）
          dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//状态转移方程
    }
  }
  cout<<dp[m]<<endl;
  return 0;
}