动态规划

动态规划

0-1背包

1. 二维dp

   • 先遍历物品还是先遍历背包重量都可以

     

     image-20240910092836809

2. 一维dp

   • 背包容量必须倒序遍历，保证物品i只被放入一次

     for(int i = 0; i < weight.size(); i++) { // 遍历物品
         for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
     
         }
     }

   • 必须先遍历物品再遍历容量，否则同一物品会被多次放入

完全背包

每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

1. 一维dp

   • 两个for循环嵌套顺序是无所谓的(因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系)

     for(int i = 0; i < weight.size(); i++) { // 遍历物品
         for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
     
         }
     }

2. 求凑出来的方案个数

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。

• 如果求排列数就是外层for遍历背包，内层for循环遍历物品