锐客网

  1. 首页 > it技术 > >

完全背包+记录路径

给定面值v，n种硬币，硬币面值为f1..fn
求凑成v所需要的硬币数，且优先使用小面值的硬币。

#include
#include
#include
using namespacestd;
const int maxn = 12;
const int maxv = 2000 + 5;
const int INF = 0x3f3f3f3f;
int dp[maxv];
int v,n;
int f[maxn];
int cnt[maxn];
int path[maxv];
int mp[maxv];


int main()
{
while (scanf("%d",&v) != EOF) {
scanf("%d",&n);
for (int i = 1; i <= n; i ++) {
scanf("%d",&f[i]);
mp[f[i]] = i;
}
memset(cnt, 0, sizeof(cnt));
dp[0] = 0;
for(int i = 1; i <= v; i ++) dp[i] = INF;

for (int i = 1; i <= n; i ++) {
for (int c = f[i]; c <= v; c ++) {
if(dp[c - f[i]] +1 <= dp[c]){//your program should output the one that uses more coins of a lower face value.
//不取等号就优先使用大面值的。
path[c] = c -f[i]; //path[c] = c - f[i]表示状态c是由c - f[i]转移来的。
dp[c] =dp[c - f[i]] +1;
}
}
}
if(dp[v] == INF) {printf("-1\n"); continue; }
int i = v;
//打印路径
if(dp[v] > 0){
while (i != 0) {
cnt[mp[i - path[i]]] ++;
i = path[i];
}
}
for (int i = 1; i <= n; i ++) {
printf("%d%c",cnt[i],i == n ? '\n' :' ');
}
}


return0;
}
https://www.jisuanke.com/contest/967/52001
【完全背包+记录路径】

    推荐阅读


    上一篇：kafka 配置文件详解（producer.properties）

    下一篇：『区间DP』Polygon