做了两道题,感觉有点懵:
P1679
P1832
完全背包的定义是:给定一个背包容量和n件物品的价值和体积,每件物品可以拿任意件。问在不超过背包容量的前提下所能拿的最大价值。
那么这两道题能用完全背包是不是都有一个前提:那就是每个数都一定可以拆分为若干个四次方数之和或若干个素数之和?(虽然这当然是正确的)
因为在原本的完全背包中背包是不一定能装满的,但是有了这样的前提后背包一定能装满所以才可以用完全背包去做