小红不想做完全背包（easy）
题目描述
本题和hard版本的唯一区别是：p保证等于3。
完全背包是一个经典问题，但小红完全不会完全背包，因此她不想做完全背包。
现在小红拿到了一个长的很像完全背包的题，她希望你帮她解决一下。
给定一个背包，有n种物品，每种物品的价值为ai，有无穷多个。小红有一个无穷大的背包她希望往里面放若干个物品，使得最终所有物品的价值之和为p的倍数。小红想知道最终至少要放多少物品？（注意：不能不放物品）
输入描述:
第一行输入两个正整数n,p，用空格隔开。第二行输入n个正整数ai。1≤n≤2000，p=3,1≤ai≤10^9.
输出描述:
一个整数，代表小红最终要放的物品数量的最小值。
输入
4 3
1 2 3 4
输出
1
说明
小红只需要选择一个第三种物品即可。
#include<iostream> #include<bits/stdc++.h> #include<vector> using namespace std; int main() { int n, p; cin>>n>>p; int a[2001]; for (int i = 0; i < n; i++) { cin>>a[i]; } int x=0,y=0,z=0; for(int i=0;i<n;i++) { if(a[i]%3==0) { x++; } if(a[i]%3==1) { y++; } if(a[i]%3==2) { z++; } } if(x!=0) { cout<<"1"; } else if(x==0&&y!=0&&z!=0){ cout<<"2"; } else{ cout<<"3"; } return 0; }
小红不想做完全背包 （hard）
p没有必须等于3的限制,1≤n,p≤2000,其余条件均一致
#include<iostream> #include<vector> #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n,p; cin>>n>>p; vector<ll>a(n); set<ll>h; bool flag=false; for(int i=0;i<n;i++){ cin>>a[i]; a[i]%=p; if(a[i]==0) flag=true; h.emplace(a[i]); } if(flag){ cout<<1; return 0; } vector<int>dist(2003,1e9); queue<pair<int,int>>q; for(auto&x:h){ dist[x]=1; q.push({dist[x],x}); } while(!q.empty()){ int s=q.front().second,cnt=q.front().first; q.pop(); for(auto&x:h){ if(dist[(s+x)%p]>cnt+1){ dist[(s+x)%p]=cnt+1; q.push({cnt+1,(s+x)%p}); } } } cout<<dist[0]; return 0; }
- 输入整数
n（序列长度）和p（模数）。 - 定义一个
vectora存储输入的整数序列，并对序列中的每个元素执行模p运算。 - 创建一个集合h 存储序列中所有元素的模
p后的唯一值，并设置一个标志变量flag，若发现0（模p后），则直接输出1（因为0本身就是目标值，不需要任何操作）并结束程序。 - 定义一个大小为
2003的vectordist，初始化所有元素为极大值1e9，用于记录从集合s中每个元素出发到达0（模p后）所需的最短步数。同时，创建一个队列q，用于广度优先搜索（BFS）算法。 - 遍历集合
s，将每个元素的初始距离（步数）设为1，并加入队列q。 - 开始执行广度优先搜索算法，循环处理队列
q中的元素，每次取出一个元素（记为s）和它的步数cnt，然后检查能否通过加这个元素s从其他元素到达新的模p后的值，并更新dist数组中的最短步数，如果新的步数小于之前的记录，则将新值和步数加入队列q。 - 当队列
q为空时，搜索结束。此时，dist[0]即为从集合s中任意一个元素出发，通过加法操作到达模p后的0所需的最短步数。 - 输出
dist[0]作为答案。
