货币系统

原题链接：https://www.acwing.com/video/388/
题意：

有n种面额的货币，第i种货币的面额为a[i]，每种货币有无数张。那么我们将这n种货币能凑成的全部面额称为一个货币系统，记为（n,a)。那么我们要找到一个货币系统(m,b)，m尽可能小，使得这个货币系统和(n,a)这个货币系统凑成的数值相等。

思路：

可以发现a数组中的每个数，都可以被b数组中的一些数凑出来。
在最优解中，b都是从a数组中选择出来的。

那么较大的数是被较小的数凑出来的，那么我们先将a数组从小到大排序之后，再对每个数进行考虑。

对第i个数来说，我们需要判断的是它能否被前面的数（1~i-1）凑出来，如果能被凑出来说明不能选择他，不能凑出来的话说明必须要选择他。

将每个数看成一种有无数个的物品，将他们的和看成是背包的容积，那么看能不能凑出a[i]，实际上就是看用前i-1种物品是否能凑出来体积等于a[i]的容量。

其实就是判断一下，装满a[i]的方案数是不是0.

f[i][j]表示能从前i个数中凑出j的方案数。那么我们只需要做一遍完全背包求方案数，然后判断每个f[i-1][a[i]]是否等于0就可以了。

朴素做法容易超时且爆空间，那么我们就优化一维，然后判断对于每个f[a[i]]的方案数是否等于1就可以了。

#include
using namespace std;
#define int long long
int n,m,p;
int f[25005];
int a[105];
void sove(){cin>>n;int mx=0;for(int i=1;i<=n;i++){cin>>a[i];mx=max(mx,a[i]);}for(int j=0;j<=mx;j++){f[j]=0;}f[0]=1;sort(a+1,a+1+n);for(int i=1;i<=n;i++){for(int j=a[i];j<=mx;j++){f[j]+=f[j-a[i]];}}int con=0;for(int i=1;i<=n;i++){if(f[a[i]]==1) con++;}cout<int t;cin>>t;while(t--){sove();}return 0;
}

混合背包问题

原题链接：https://www.acwing.com/problem/content/7/
有n种物品和一个容量是m的背包，类型有3种：
1.第一种物品只能用一次
2.第二种物品可以用无限次
3.第三种物品只能用si次
求物品体积总和不超过背包容量，能装的最大价值。

思路：
完全背包的转移公式：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])
多重背包的转移公式：f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i])
01背包是特殊的多重背包，将si设为1即可
那么对于多重背包，我们将他进行一个二进制优化，将他分成多个背包之后再进行01背包的转换。

#include
using namespace std;
const int N=2000;
int n,m;
int f[N];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;if(s==0){for(int j=v;j<=m;j++){f[j]=max(f[j],f[j-v]+w);}}else{if(s==-1) s=1;for(int k=1;k<=s;k*=2){for(int j=m;j>=k*v;j--){f[j]=max(f[j],f[j-k*v]+w*k);}s-=k;}if(s>0){for(int j=m;j>=s*v;j--){f[j]=max(f[j],f[j-s*v]+s*w);}}}}cout<

#include
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m;
const int N=1005;
int f[N][N];
int g[N][N];
int v[N],w[N];
signed main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];memset(f,-0x3f,sizeof f);for(int i=0;i<=n;i++) g[i][0]=1;for(int j=0;j<=m;j++)g[0][j]=1;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];g[i][j]=g[i-1][j];if(j>=v[i]){if(f[i-1][j-v[i]]+w[i]>f[i][j]){f[i][j]=f[i-1][j-v[i]]+w[i];g[i][j]=g[i-1][j-v[i]];}else if(f[i-1][j-v[i]]+w[i]==f[i][j]){g[i][j]=(g[i][j]+g[i-1][j-v[i]])%mod;}}}}cout<

#include
using namespace std;
int n,m;
const int N=1005;
int f[N][N];
int g[N][N];
int v[N],w[N];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>v[i]>>w[i];for(int i=n;i>=1;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+1][j-v[i]]+w[i]);}}int j=m;for(int i=1;i<=n;i++){if(j>=v[i]){if(f[i+1][j-v[i]]+w[i]>=f[i+1][j]){cout<