关于路径打印的一个疑问

本来以为若存在唯一解,那么在记录前驱的时候只管直接记录就好
'''c++
for(int i = 1; i <= n; ++i)
for(int j = prefix[i]; j >= val[i]; --j)
if(dp[j - val[i]] != inf){
if(dp[j] == inf) dp[j] = dp[j - val[i]];
else dp[j] += dp[j - val[i]];
pre[j] = i;
}
'''
可是这样第四个点过不去
后来把路径记录修改一下就AC了,可是想不明白这是为什么
'''c++
for(int i = 1; i <= n; ++i)
for(int j = prefix[i]; j >= val[i]; --j)
if(dp[j - val[i]] != inf){
if(dp[j] == inf) dp[j] = dp[j - val[i]], pre[j] = i;
else dp[j] += dp[j - val[i]];
}
'''

请大神赐教

1 条评论

  • @ 2017-11-29 18:47:39

    这样会导致多个j的pre值都为i, 有可能会出现重复打印一张牌的情况

    • @ 2017-11-30 15:16:53

      明白了!十分感谢!

  • 1

信息

ID
1071
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
5572
已通过
1277
通过率
23%
上传者