背包问题的初始化问题

对于背包问题&＃xff0c;有两种初始化问题。。。。

一种是恰好装满&＃xff0c;另一种是实际上可以不装满&＃xff0c;其中还分概率&＃xff08;乘&＃xff09;与非概率&＃xff08;加&＃xff09;

 

其实不管是哪种&＃xff0c;记住一点&＃xff0c;我们初始化是未放物品时符合条件的最优解。。。。。

 

例如&＃xff1a;

1~恰好装满&＃xff1a;f[0] &＃61; 0没放物品时价值是0&＃xff0c;&＃xff0c;&＃xff0c;f[1....]不符合条件&＃xff08;因为要恰好装满&＃xff09;&＃xff0c;这些都是没装满的

那这些应该赋什么值呢&＃xff1f;应该赋最不优的解来保证一定更新它。。。。。求最大&＃xff1a;(求最大的时候最不优就是最小)概率&＃xff08;乘&＃xff09;f[1....] &＃61;  0(乘中0最小)    非概率&＃xff08;加&＃xff09;f[1...] &＃61; -INF&＃xff08;加中-INF最小&＃xff09;

 

求最小&＃xff1a;&＃xff1a;(求最小的时候最不优就是最大)概率&＃xff08;乘&＃xff09;f[1....] &＃61;  1(乘中1最大)    非概率&＃xff08;加&＃xff09;f[1...] &＃61; INF&＃xff08;加中INF最大&＃xff09;

 

 

2~不需要装满的:非概率&＃xff08;加&＃xff09;求最大优解&＃xff1a;memset(f, 0, sizeof(f));....................