灵鹊做题网pascal 0/1背包和完全背包的差别?
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：综合作业 时间：2024/04/29 12:45:46
pascal 0/1背包和完全背包的差别?
0/1背包?
for i:=1 to n do
for j:=m downto w[i] do
完全背包?
for i:=1 to n do
for j:=w[i] to m do
两个什么差别?怎么体现?
有没有样例可以体现两个的差别?就是输入一样,输出不一样.
为什么倒着取就是一次?
不倒着取就可能不是只取一次?
0/1背包?
for i:=1 to n do
for j:=m downto w[i] do
完全背包?
for i:=1 to n do
for j:=w[i] to m do
两个什么差别?怎么体现?
有没有样例可以体现两个的差别?就是输入一样,输出不一样.
为什么倒着取就是一次?
不倒着取就可能不是只取一次?
顺序反了,那么在完全背包中就可以多次取同一物品
因为这是一维数组
f[n]=a[m]+w 那么到f[n+m]时,f[n+t[m]]可以取f[n]+a[m]但0/1只能取一次（因为是倒着取的）
因为这是一维数组
f[n]=a[m]+w 那么到f[n+m]时,f[n+t[m]]可以取f[n]+a[m]但0/1只能取一次（因为是倒着取的）