首页 > 代码库 > Codeforces 788C The Great Mixing（背包问题建模+bitset优化或BFS）
Codeforces 788C The Great Mixing（背包问题建模+bitset优化或BFS）
【题目链接】 http://codeforces.com/problemset/problem/788/C
【题目大意】
给出一些浓度的饮料，要求调出n/1000浓度的饮料，问最少需要多少升饮料
【题解】
设浓度为a，现在要求出系数x1,x2,x3……，使得x1*a1+x2*a2+x3*a3+……=n*(x1+x2+x3+……)
得a1*(x1-n)+a2*(x2-n)+a3*(x3-n)+……=0
假设现在有x1-n和x2-n，设其数值为x和y，那么一定有(x)*y+(-y)*x=0,
x+y=x-(-y)<1000，更多物品的答案不会超过两个物品，所以答案最多1000，
那么现在就是背包问题容量0是否能被覆盖到，因为状态只有两种，是否被覆盖，
所以我们可以用bitset优化。
同时，我们发现这个最小答案相当于求最短路的过程，每次可以有一定的步长，
问到达目标状态的最小值，所以可以将每种物品作为步长，用bfs来解决背包问题。
【代码】
#include <cstdio>#include <cstring>#include <algorithm>#include <bitset>#include <vector>using namespace std;typedef long long LL;int x,n,k;int main(){ scanf("%d%d",&n,&k); vector<bool> vis(1001,0); for(int i=1;i<=k;i++){ scanf("%d",&x); vis[x]=1; }vector<int> v; for(int i=0;i<=1000;i++)if(vis[i])v.push_back(i-n); bool flag=0; bitset<2010>cur,nxt; cur[1000]=1; for(int i=1;i<=1000&&!flag;i++){ nxt.reset(); for(int x=0;x<v.size();x++){ if(v[x]>0)nxt|=cur<<v[x]; else nxt|=cur>>-v[x]; }swap(cur,nxt); if(cur[1000]){flag=1;printf("%d\n",i);} }if(!flag)puts("-1"); return 0;}#include <cstdio>#include <vector>#include <queue>using namespace std;int n,k,x;int main(){ scanf("%d%d",&n,&k); vector<bool> vis(1001,0); for(int i=1;i<=k;i++){ scanf("%d",&x); vis[x]=1; }vector<int> vs; for(int i=0;i<=1000;i++)if(vis[i])vs.push_back(i-n); vector<int> dp(2010,-1),q; for(int i=0;i<vs.size();i++){ int u=vs[i]+1000; dp[u]=1; q.push_back(u); } for(int i=0;i<q.size();i++){ int u=q[i]; for(int x=0;x<vs.size();x++){ int v=u+vs[x]; if(v>=0&&v<=2000&&dp[v]<0){ dp[v]=dp[u]+1; q.push_back(v); } } }printf("%d\n",dp[1000]); return 0;}
Codeforces 788C The Great Mixing（背包问题建模+bitset优化或BFS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。