https://ac.nowcoder.com/acm/problem/21228
题意:
有n种货币,每种货币数量无限,问能否删掉几种货币,使得原来能组成的数现在仍能组成。
分析:
想要去掉某种硬币,说明它可以被一种或多种面值比它小的货币所组成,一个或多个的和能组成某一个数,明显的背包问题,而且每个类型的货币数量无限,因此这题是一个完全背包问题。
由于每个货币只能由面值比它小的共同组成,所以我们应该先对给定货币面额进行正序排序,然后一个个判断拿还是不拿,如果发现当前面额能被组成,我们直接不管即可,如果发现不能组成,则进行状态转移把它范围内能组成的所有数标记一下即可。
状态转移方程为:dp[j] = dp[j] | dp[j-a[i]]
代码:
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<set> using namespace std; typedef long long ll; int i,j,cnt,n,k,t,b,m,x,ans; using namespace std; int a[105],dp[25005]; int main() { scanf("%d",&t); while(t--){ ans=0; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&a[i]); } sort(a,a+n); dp[0]=1; for(i=0;i<n;i++){ if(!dp[a[i]]) ans++;//无法组成放进去 else continue;//能组成不管了 for(j=a[i];j<=25000;j++){ dp[j]|=dp[j-a[i]];//dp[j]由dp[j-a[i]]转移过来的 } } printf("%d\n",ans); } }