动态规划2-背包DP

装箱问题

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入描述:一个整数v,表示箱子容量;一个整数n,表示有n个物品;接下来n个整数,分别表示这n 个物品的各自体积
输出描述:一个整数,表示箱子剩余空间。
样例输入: 24 6
​ 8 3 12 7 9 7
样例输出:0

动态规划1

笔记

最优子结构:子结构最优,全局一定最优
无后效性:各个决策部分单独存在,不会相互影响

  1. 确定状态
    • 维度从低往高试
  2. 确定转移方程
    • 每一个状态的决策
    • 初始值
    • 边界问题
  3. 是否可以降低维度或其他优化
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×