图解四种常见背包问题及优化方式-创新互联

背包分类

每 件/种 物品体积Vi
不超过背包容量的总价值大化W(不一定装满)

创新互联-专业网站定制、快速模板网站建设、高性价比沛县网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式沛县网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖沛县地区。费用合理售后完善,十年实体公司更值得信赖。
  • 01 背包:每件物品最多只用一次
  • 完全背包:每件物品无限个
  • 多重背包:每件物品有限ai个
  • 分组背包:从每组选择一个
01背包与动态规划思路在这里插入图片描述

代码实现(二维朴素法)

在这里插入图片描述

#include#include
using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];//默认初始为0
int dp[N][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++) {	dp[i][j] = dp[i-1][j];
			if(j>=v[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);
		}
	cout<

代码实现(滚动数组,转态压缩)

在这里插入图片描述

#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int dp[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 = m; j >= v[i]; j--) {	//这里空集部分判断直接挪到循环里面
	    	//不用推导,直接继承上一层
	    	dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
		}
	cout<

完全背包与数列推导优化

最朴素的思路起点

在这里插入图片描述

代码实现(显然会超时,1000三次方过亿次了,C++的 1s 大体运行一亿次)

在这里插入图片描述

#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][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++)
              f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<< f[n][m]<

DP常见的数列推导优化

推导递推公式,常减去一项来观察规律实现降维。
在这里插入图片描述

#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][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++) {   f[i][j] = f[i-1][j];
           if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
       }
           
    cout<< f[n][m]<

状态压缩

区分 01背包(全上层) 和 完全背包(本层+上层) 的遍历顺序。
在这里插入图片描述

#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[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 = v[i]; j<= m; j++) {   f[j] = max(f[j],f[j-v[i]]+w[i]);
       }
           
    cout<< f[m]<

多重背包与二进制枚举优化

在这里插入图片描述

最朴素的思路起点(如果数据过大和完全背包一样超时)

在这里插入图片描述

#include#include

using namespace std;

const int N = 110;

int n,m;
int v[N],w[N],s[N];
int f[N][N];

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) cin >>v[i] >>w[i] >>s[i];
    
    for(int i = 1; i<= n; i++)
       for(int j = 0; j<= m; j++) 
          for(int k = 0; k*v[i]<= j && k<= s[i]; k++) {  f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
          }
    cout<< f[n][m]<

二进制枚举优化

比如要枚举0->1023中所有的数能不能凑成其中任意一个数
我们平常的枚举方法就是:0,1,2,3,4,5,…,1023。这样枚举1024次
使用二进制枚举优化,就可以只需枚举10次就可以枚举出任意一个数。
将0~1023这1024个数分为10个组,
每组分别是:1 2 4 8 16 32 64 128 256 512 这10个数字(2^0 2^1 2^2 … 2^9)。
在枚举的时候只枚举这10个数字,选或不选。就可以枚举出0~1023中的任意一个数字
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

二进制枚举优化代码实现

在这里插入图片描述

#include#include

using namespace std;

const int N = 25000;

int n,m;
int v[N],w[N];
int f[N];

int main() {cin >>n >>m;
    int cnt = 0;
    for (int i = 1; i<= n; i++) {int a,b,s;
        cin >>a >>b >>s;
        int k = 1;
        while(k<= s) {cnt++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if(s >0) {cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= v[i]; j--)
          f[j] = max(f[j],f[j-v[i]] + w[i]);
          
    cout<< f[m]<< endl;
    return 0;
}

分组背包与状态压缩总结

在这里插入图片描述

和01背包特别像,不过多一个组内选择

在这里插入图片描述

状态压缩以及遍历顺序的总结

只要是上一层推导的,则从后往前
如果是同层推导的,则从前往后
只要是由上层某个方向定向推来的,就可以进行状态压缩

代码实现
#include#include

using namespace std;

const int N = 110;

int v[N][N],w[N][N],s[N];
int f[N];
int n,m;

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) {cin >>s[i];
        for(int j = 1; j<= s[i]; j++) {cin >>v[i][j] >>w[i][j];
        }
    }
    
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= 0; j--)
           for(int k = 1; k<= s[i]; k++)
              if(j >= v[i][k]) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<< f[m]<< endl;
    return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前标题:图解四种常见背包问题及优化方式-创新互联
浏览路径:http://myzitong.com/article/pedss.html