本文为题解集

P2347 砝码称重
P5020 货币系统

祭

来一个祭：

屈指可数的一遍过的题——P5020 货币系统

我太蒻了。

P2347 砝码称重

题目描述

设有 $1g$ 、 $2g$ 、 $3g$ 、 $5g$ 、 $10g$ 、 $20g$ 的砝码各若干枚（其总重 $\le1000$ ），

输入格式

输入方式： $a_1$ , $a_2$ , $a_3$ , $a_4$ , $a_5$ , $a_6$

（表示 $1g$ 砝码有 $a_1$ 个， $2g$ 砝码有 $a_2$ 个，…， $20g$ 砝码有 $a_6$ 个）

输出格式

输出方式： $Total=N$

（ $N$ 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

暴力：

#include <bits/stdc++.h>
#define _ 0
using namespace std;
int v[1005],m[10],tmp=0,ans=0;
int main()
{
    for(int i=1;i<=6;i++)
    	scanf("%d",&m[i]);
    for(int a=0;a<=m[1];a++)
        for(int b=0;b<=m[2];b++)
            for(int c=0;c<=m[3];c++)// C++: ???
                for(int d=0;d<=m[4];d++)
                    for(int e=0;e<=m[5];e++)
                        for(int f=0;f<=m[6];f++)
                            tmp=a+b*2+c*3+d*5+e*10+f*20,v[tmp]=1;
    for(int i=1;i<=1000;i++)
    	ans+=v[i];
    printf("Total=%d",ans);
    return ~~(0^_^0);//嘤嘤嘤
}

然鹅，只有 72pts。~~对啊， $6$ 层 for 循环能不 TLE 吗？~~

一个思路：

设有 $1g$ 、 $2g$ 、 $3g$ 、 $5g$ 、 $10g$ 、 $20g$ 的砝码各若干枚

即表示 $1g$ 砝码有 $a_1$ 个， $2g$ 砝码有 $a_2$ 个，…， $20g$ 砝码有 $a_6$ 个

emm…这不就是多重背包吗？

我们可以设有 $max$ 个背包，整齐地排成一行，分别可以承重 $1,2,3,...,\max$ （其中 $\max$ 指所有砝码的重量）。

跑一遍多重背包，数一下各个背包，有几个背包放满了砝码（bag[i]==i）！

补充更新：这其实是可行性 dp。状态转移方程的逻辑是：既然 bag[i] 是合法的，那么在 $i$ 的基础上再加一个砝码也是合法的。

#include<bits/stdc++.h>
#define _ 0
using namespace std;
int w[]={0,1,2,3,5,10,20},a[10],f[1005];
int main()
{
	int ans=0;
	for(int i=1;i<=6;i++)
		scanf("%d",&a[i]);
    for(int i=1;i<=6;i++)//dp,多重背包
	 	for(int j=1000;j>=w[i];j--)
    		for(int k=1;k<=a[i];k++)
    			if(j>=k*w[i])
	   				f[j]=max(f[j],f[j-k*w[i]]+k*w[i]);
	for(int i=1;i<=1000;i++)
		if(f[i]==i)
			ans++;
    printf("Total=%d",ans);
  	return ~~(0^_^0);//嘤嘤嘤
}

P5020 货币系统

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a_i$ ，你可以假设每一种货币都有无穷多张。

emm…类似地，你也可以把它转化为背包问题，基本思路与上题差不多！

code

po 一下 $\color{red}{\texttt{code}}$ ：

#include<bits/stdc++.h>
#define _ O//这次会CE!为什么?显而易见!
using namespace std;
int t,n,a[100+5],f[25000+5],ans,ins[25000+5];
void work()
{
	for(int i=1;i<=n;i++)
	 	for(int j=a[i];j<=a[n];j++)//小小剪枝，只需枚到货币面额的最大值。
	 	{
	 		f[j]=max(f[j],f[j-a[i]]+a[i]);
	 		if(f[j]==j&&f[j-a[i]]!=0)//f[j]的状态不是由空背包状态转移来，即不是被本面额表示
	 			ins[j]=1;
		}
	return;		
}	
int main()
{ 
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		memset(f,0,sizeof(f)),memset(ins,0,sizeof(ins));//记得清0啊啊啊
		scanf("%d",&n),ans=n;
		for(int j=1;j<=n;j++)
			scanf("%d",&a[j]);
		sort(a+1,a+1+n),work();
		for(int j=1;j<=n;j++)
			ans-=ins[a[j]];//简写 等价于 if(ins[a[j]])ans--;
		printf("%d\n",ans);
	} 
	return ~~(0^_^0);//嘤嘤嘤
}
/*
此code有许多需改进的地方，比如需要排序。
访者可思考如何做可不用排序。
https://henryhuang.blog.luogu.org/solution-p5020
*/

思路

ins[]：instead，是否可以被现有货币表示出，且不是只用一张货币。

f[]：背包。

证明：$ B \subseteq A$

设有两个货币系统 $(n,a)$ 和 $(m,b)$ 。

首先，我们需证明：为什么不能添加新的货币面额，而只能减少现有货币面额种类？

即，设 $(n,a)$ 为集合 $A$ ， $(m,b)$ 为集合 $B$ ，为什么 $ B \subseteq A$？

这里，引用大佬的证明，链接here：

------------------------------以下为引用内容------------------------------

在证明这个猜测前我们先来证明另一个猜测 $A$ 集合内不能被其它数组成的数必然存在于 $B$ 集合内，这里使用反证法证明。

证明过程

我们设 $x\in A$ 且 $x$ 不能被 $A$ 集合内除它以外的元素组成。

然后我们假设 $x \notin B$ ，那么就说明 $B$ 集合中必然存在一些元素能够组成 $x$ 。

那么这些元素至少存在一个不在集合 $A$ 内并且不能被集合 $A$ 里的元素组成的数（因为如果不存在的话集合 $A$ 内的元素就可以组成 $x$ 了），可以看到这与集合 $B$ 的定义产生了矛盾。

综上所述， $A$ 集合内不能被其它数组成的数必然存在于 $B$ 集合内 。证毕。

通过这个结论我们便可以证明 $B \subseteq A$ 这个猜测了。这里同样使用反证法证明。

证明过程

假设存在 $x \in B$ 且满足 $x \notin A$ 。

根据题目条件， $x$ 必然可以被 $A$ 集合内的数字所组成。

那么必然存在 $a_1,a_2,...a_q \in A$ 可以用来组成 $x$ 并且这些元素都不能被 $A$ 集合内的元素组成（因为如果 $a_i$ 能被 $A$ 集合内其它数组成，那么必然可以用那些数来代替 $a_i$ ），根据上一个结论我们可以知道 $a_1,a_2,...a_q \in B$ 。