已知有n个包,和总共s个钱币。 n,s<=70000.
每个包可以装钱币,还可以套别的包。每个包中的钱数等于 所有套的包的钱数 加上 自己装的钱。
所有的钱都在包内。
问给定每个包中的钱数,输出方案。
当方案不存在时,输出-1。
==========
乍一看好像是树,包就是结点,钱就是权值。
然后会发现可以转二叉树,即每个包,如果要套包,只套一个包。
然后就变成了简单的背包问题,求,给定n个包中各有ai枚钱币,求拿一些包使得总钱数等于s。
2024-02-25 22:09:51
已知有n个包,和总共s个钱币。 n,s<=70000.
每个包可以装钱币,还可以套别的包。每个包中的钱数等于 所有套的包的钱数 加上 自己装的钱。
所有的钱都在包内。
问给定每个包中的钱数,输出方案。
当方案不存在时,输出-1。
==========
乍一看好像是树,包就是结点,钱就是权值。
然后会发现可以转二叉树,即每个包,如果要套包,只套一个包。
然后就变成了简单的背包问题,求,给定n个包中各有ai枚钱币,求拿一些包使得总钱数等于s。