背包组合数相关

总结

背包组合问题通常用01背包dp解决
相关问题有数组中的数字求单次组合数和无限次组合数
前者用dp[i]表示i的组合数有dp[i]种 接着逆序遍历所有数字用dp[i]+=dp[i-k]更新
无限次更新通过hash和背包思想 通常问是否能组合某个数字或者所有数字
还可用bitset s|=s<<num[i]表示把第个数字压入bitset中 最后判断第i位的数字是否为1就代表是否能取到

HDU 6092

通过所有组合数的个数反推集合中的每个元素
多校5转跳链接

openjudge 2985

题目要求

给出大小为n的数组 单次组合后问和为t的组合数有多少种组合方式

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
int dp[maxn];
int main(){
	int n,t; 
	cin>>n>>t;
	memset(dp,0,sizeof dp);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		for(int j=t;j>=x;j--) dp[j]+=dp[j-x];
	}
	cout<<dp[t]<<endl;
	return 0;
}

思路

逆序更新dp 每次跳的间隔就是数字的大小

HDU 5890

有限制条件的(每次不允许取某3个数字)下的取10个数字 问和是否能等于87
bitset+预处理dp
转跳链接

2017蓝桥杯B组第八题

题目要求

求n个数字的无限次组合后是否能取到所有的正数
有限个输出答案 无限个输出INF

参考伪代码

1
2
3
4
5

for(int i=1;i<=n;i++){
	for(int j=0;j+num[i]<N;j++){
		if(hashh[j]) hashh[j+num[i]]=1;
	}
}

思路

exgcd变形+背包
如果n个数字的gcd>1 直接输出INF
伪代码中的N取到10000即可 开始hashh初始化为0 hashh[0]=1即可
最后判断hashh中0的个数就是答案