题目 | 类型 |
---|---|
1、数字组合 | 01背包 |
2、买书 | 完全背包 |
3、 货币系统1 | 完全背包 |
4、货币系统2 | 完全背包 |
1、数字组合
给定 N个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。
输入格式第一行包含两个整数 N和 M。
第二行包含 N个整数,表示 A1,A2,…,AN。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。
输入样例:
4 4
1 1 2 2
输出样例:
3
思路:
01背包模型,状态转移方程一样,唯独属性是方案数,只是每次转移的时候加上上一个状态的方案数即可(而不是之前的取最大值)
状态转移方程:
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i-1][j-w[i]];
代码:
#include<bits/stdc++.h>
using namespace std;
//f[i][j]表示选i个数,总和为j的集合,属性:方案数
const int N=103;
int w[N];
int f[N][10010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=0;i<=n;i++)f[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i-1][j-w[i]];
}
}
cout<<f[n][m];
return 0;
}
2、买书
小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。
问小明有多少种买书方案?(每种书可购买多本)
输入格式
一个整数 n,代表总共钱数。
输出格式
一个整数,代表选择方案种数。
数据范围
0≤n≤1000
输入样例1:
20
输出样例1:
2
输入样例2:
15
输出样例2:
0
输入样例3:
0
输出样例3:
1
思路:
每一种书能买无数本,就相当于完全背包问题
状态转移方程:
f[i][j]+=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i][j-w[i]];
代码:
朴素版:
//完全背包问题
#include<bits/stdc++.h>
using namespace std;
const int N=1003;
int w[5];
int f[N][N];//f[i][j]表示选i本书,容量为j的选法
int main()
{
w[1]=10,w[2]=20,w[3]=50,w[4]=100;
int n;
cin>>n;//背包容量
f[0][0]=1;
for(int i=1;i<=4;i++)
{
for(int j=0;j<=n;j++)
{
f[i][j]+=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i][j-w[i]];
}
}
cout<<f[4][n];
return 0;
}
优化掉一个维度:
//完全背包问题
#include<bits/stdc++.h>
using namespace std;
const int N=1003;
int w[5];
int f[N];//f[i][j]表示选i本书,容量为j的选法
int main()
{
w[1]=10,w[2]=20,w[3]=50,w[4]=100;
int n;
cin>>n;//背包容量
f[0]=1;
for(int i=1;i<=4;i++)
{
for(int j=0;j<=n;j++)
{
if(j>=w[i])f[j]+=f[j-w[i]];
}
}
cout<<f[n];
return 0;
}
3、货币系统1
给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。
输入格式
第一行,包含两个整数n和m。
接下来n行,每行包含一个整数,表示一种货币的面值。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
n≤15,m≤3000
输入样例:
3 10
1
2
5
输出样例:
10
思路:
仍然是完全背包模型,经典转移方程即可解决
属性:方案数
状态转移方程:
f[i][j]+=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i][j-w[i]];
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=18;
int w[N];
long long f[N][3003];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
//完全背包问题
//初始化
f[0][0]=1;//0种面值组成0总价值的方案为1
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j]+=f[i-1][j];
if(j>=w[i])f[i][j]+=f[i][j-w[i]];
}
cout<<f[n][m];
return 0;
}
4、货币系统2
在网友的国度中共有 n种不同面额的货币,第 i种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。
为了方便,我们把货币种数为 n、面额数组为 a[1…n]的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x都应该可以被表示出,即对每一个非负整数 x,都存在 n个非负整数 t[i]满足 a[i]×t[i]的和为 x。
然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x不能被该货币系统表示出。
例如在货币系统 n=3, a=[2,5,9]中,金额 1,3就无法被表示出来。
两个货币系统 (n,a)和 (m,b)是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统 (m,b),满足 (m,b)与原来的货币系统 (n,a)等价,且 m尽可能的小。
他们希望你来协助完成这个艰巨的任务:找到最小的 m。
输入格式
输入文件的第一行包含一个整数 T,表示数据的组数。
接下来按照如下格式分别给出 T组数据。
每组数据的第一行包含一个正整数 n。
接下来一行包含 n个由空格隔开的正整数 a[i]。
输出格式
输出文件共有 T
行,对于每组数据,输出一行一个正整数,表示所有与 (n,a)等价的货币系统 (m,b)中,最小的 m。
数据范围
1≤n≤100,1≤a[i]≤25000,1≤T≤20
输入样例:
2
4
3 19 10 6
5
11 29 13 19 17
输出样例:
2
5
思路:
最初的朴素思路:
把所有的面值按从小到大排序,如果一个面值能被前面的面值组合起来,那么这个面值可以被优化掉(事实证明这个思路是正确的),然后对每种面值求是否能被组合出来,如果能被组合出来那就记录一下,最后总面值减去能被组合出来的面值的数量
优化后的思路:
*实际上是一个线性代数问题:求向量组的最大无关向量组
现在我们用f[j]来存储bool值,表示j的面值能否被凑出来
步骤:
1、枚举每一种面值,然后开始筛选
2、如果是true,则表示当前的面值能被表示出来,continue
3、如果是false,则表示当前的面值不能被表示出来,res++,并且用当前的面值来筛选未来的面值是否能被表示出来**
代码:
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,string>m;//codeblocks-c++11 哈希表正常使用
typedef long long LL;
const int N=103;
int w[N];//每一种面值都有无穷多张,可以看作完全背包问题
//思路:
//排序,如果后面的大面值的货币能被前面的小面值的货币凑出来,那么这个面值是可以去掉的
//那么集合的状态就+1
//最后用n减去状态集合表示的值就可以了
//集合表示:
bool f[25002];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
sort(w+1,w+n+1);
// for(int i=2;i<=n;i++)
// {
// memset(f,0,sizeof f);
// f[0][0]=1;
// for(int j=1;j<=i;j++)
// {
// for(int k=0;k<=w[i];k++)
// {
// f[j][k]+=f[j-1][k];
// if(k>=w[j])
// {
// f[j][k]+=f[j][k-w[j]];
// if(f[j][k]!=0)res++;
// }
// }
// }
// }
int res=0;//最大向量无关组
int m=w[n];
memset(f, 0, sizeof f);
f[0]=true;
for(int i=1;i<=n;i++)
{
if(f[w[i]])continue;
res++;
for(int j=w[i];j<=m;j++)
{
f[j]|=f[j-w[i]];
}
}
cout<<res<<endl;
}
return 0;
}