现实酸奶

文章
10
资源
0
加入时间
2年10月17天

背包问题求方案数(最大价值的方案数)思路:

原题链接思路:求最大价值的同时更新最大方案;因为所有不放物品也算一种方案,所以初始化所有cnt[i]=1cnt[i] = 1cnt[i]=1如果f[j−v[i]]>f[j]f[j - v[i]] > f[j]f[j−v[i]]>f[j] 说明用当前物品的体积比不用当前物品的体积大,那就先更新最大价值,使f[j]=f[j−v[i]]+w[i]f[j] = f[j - v[i]] + w[i]f[j]=f[j−v[i]]+w[i],同时更新cnt[j]cnt