[POI2005]BAN-Bank Notes [多重背包]

本文主要是介绍[POI2005]BAN-Bank Notes [多重背包]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

二进制拆分 , 然后f[j] 表示到j的最少钱币 

用一个bool数组记录是否转移

---

#include<bits/stdc++.h>
#define N 205
#define M 20050
using namespace std;
int n,f[M],b[N],c[N],k,tot;
struct Node{int w,v,val;}a[N*16];
bool from[N*16][M]; int ans[M],vis[M];
void dfs(int now,int val){if(now==0 || val==0) return;while(!from[now][val]) now--;val -= a[now].val;ans[a[now].w] += a[now].v;now--; dfs(now,val);
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&b[i]),vis[b[i]]=1;for(int i=1;i<=n;i++){scanf("%d",&c[i]); int x=c[i];for(int k=1;k<=x;k<<=1)a[++tot]=(Node){b[i],k,b[i]*k},x-=k;if(x) a[++tot]=(Node){b[i],x,b[i]*x};}memset(f,127,sizeof(f)); f[0]=0;scanf("%d",&k);for(int i=1;i<=tot;i++){for(int j=k;j>=a[i].val;j--){if(f[j-a[i].val] + a[i].v < f[j]){f[j] = f[j-a[i].val] + a[i].v;from[i][j] = 1;}}}printf("%d\n",f[k]); dfs(tot,k);for(int i=1;i<=20000;i++) if(vis[i]) printf("%d ",ans[i]);return 0;
}

 

这篇关于[POI2005]BAN-Bank Notes [多重背包]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---