2020-2021:teams:manespace:背包问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:manespace:背包问题 [2020/07/16 16:05] iuiou 创建 |
2020-2021:teams:manespace:背包问题 [2020/07/16 16:08] (当前版本) iuiou |
||
|---|---|---|---|
| 行 27: | 行 27: | ||
| 上面是01背包，每个物品选一次。 | 上面是01背包，每个物品选一次。 | ||
| - | 可重背包：只需要改成for(int j=a[i];j<=v;j--)即可 | + | *可重背包：只需要改成 |
| + | <code c++> | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | for(int j=a[i];j<=v;j--) | ||
| + | { | ||
| + | dp[j]=max(dp[j],dp[j-a[i]]+a[i]); | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| - | 多重背包：即限定了每种的个数，可以考虑转化为01背包，把相同的看成一个，还可以采用二进制分组的方法，简化复杂度。 | + | *多重背包：即限定了每种的个数，可以考虑转化为01背包，把相同的看成一个，还可以采用二进制分组的方法，简化复杂度。 |
| - | 分组背包：有许多组，每组有若干个，每组只能选一个。最外面枚举组别，考虑在最里面一层再加入一个循环判断选这个组哪个物品。 | + | *分组背包：有许多组，每组有若干个，每组只能选一个。最外面枚举组别，考虑在最里面一层再加入一个循环判断选这个组哪个物品。 |
| - | 有依赖背包：即选一个必选依附的那一个，转化状态即可，将不同的状态看成物品，即加入选b或选c就要选a，可以直接转化为只选a，只选a和b，只选a和c，选则a,b,c这样四种情况，分别看作一种物品，做分组背包即可。 | + | *有依赖背包：即选一个必选依附的那一个，转化状态即可，将不同的状态看成物品，即加入选b或选c就要选a，可以直接转化为只选a，只选a和b，只选a和c，选则a,b,c这样四种情况，分别看作一种物品，做分组背包即可。 |
| - | 背包问题大致就上面这些。 | + | 背包问题大致就上面这些,还有都是这些问题的变式，也大致基于上面所说的核心转移方程。 |
| | | ||
| | | ||
2020-2021/teams/manespace/背包问题.1594886743.txt.gz · 最后更改: 2020/07/16 16:05 由 iuiou
