背包问题-【01背包】【完全背包】【多重背包】【多限定条件背包】

背包问题

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

可参考https://www.cnblogs.com/-guz/p/9866118.html

1. 0-1背包问题[求最大的价值，不要求恰好装满这个包]

我们有n种物品，物品i的重量为weight[i]，价格为value[i]。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为total。如果限定每种物品只能选择0个或1个，求背包里面能放的最大价格。

dp[i][v]代表“将前i件物品放入容量为v的背包中得到的最大价值。

情况1：第i件不放进去，转化成前i-1件物品放入容量为v的背包中的价值的情况，此时所得价值

       dp[i-1][v]

情况2：第i件放进去，要是容量只能为v,则可以转化成将前i-1件物品放入v-weight[i]的背包里，此时加入第i件的重量恰好是v重量的背包，所得价值

       dp[i-1][v-weight[i]] + c[i]，

由此得到状态转移方程：注：dp[i][v]表示重量不超过v公斤的最大价值

  dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-w[i]]+c[i])

时间和空间复杂度都为O(Num*total)=O(N*N),可以将其压缩成空间为O(total) = O(N)

• 情况1：第i件不放进去，所得价值dp[v]
• 情况2：第i件放进去，所得价值dp[v-weight[i]]+c[i]

由此得到状态转移方程：dp[v]表示重量不超过v公斤的最大价值
     dp[v] = Math.max(dp[v],dp[v-w[i]]+c[i])

>     //weight表示每件物品的重量，value代表每件物品的价值，total 表示容量，Num表示物品数量，设 dp[v]表示重量不超过v公斤的最大价值
>     public static int ZeroOnePackage(int []weight,int []value,int []dp,int Num,int total){
>         for(int i = 0;i<Num;i++){
>             for(int v = total;v>=weight[i];v--){ //注意是逆序
>                 dp[v] = Math.max(dp[v-weight[i]]+value[i],dp[v]);
>             }
>         }
>         return dp[total];
>     }
>

关于为什么是逆序：https://www.jb51.net/article/126072.htm

• 如果只用一个数组dp[0…V]，要保证每次主循环中我们要以v = V…0的顺序推dp[v],才能保证推dp[v]时dp[v-weight[i]]保存的状态是dp[i-1][v-weight[i]]的值，
• 因为如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-weight[i]]推出了而不是f[i-1][v-weight[i]]

2. 0-1背包问题[要求恰好装满这个包，此时的最大价值]

 与以上不同初始化时除了f[0]为0其它f[1..V]均设为-∞，可以这样理解，可以这样理解：初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。

 如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。

 如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

> public static int ZeroOnePackage(int []weight,int []value,int Num,int total){
>        int dp[] = new int[total+1];
>        //初始化dp数组
>        for(int i = 1;i<dp.length;i++)
>            dp[i] = Integer.MIN_VALUE; 
>        //动态规划背包问题
>       for(int i = 0;i<Num;i++){
>           for(int v = total;v>=weight[i];v--){ //注意是逆序
>               dp[v] = Math.max(dp[v-weight[i]]+value[i],dp[v]);
>           }
>       }
>       return dp[total];
>   }
>

2. 完全背包问题

有Num种物品和一个容量为total的背包，每种物品都有无限件可用。第i种物品的体重量是weight[i]，价值是value[i]。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

 情况1：第i件不放进去，所得价值 dp[i-1][v]

 情况2：第i件放进去，所得价值 dp[i-1][v-weight[i]]+c[i]

由此得到状态转移方程：，dp[i][v]表示前i个背包装入重量不超过v公斤的最大价值

dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-n*w[i]]+n*c[i]){0<n*value[i]<total}

时间和空间复杂度都为O(Num*total)=O(N*N),可以将其压缩成空间为O(total) = O(N)

• 情况1：第i件不放进去，所得价值dp[v]
• 情况2：第i件放进去，所得价值dp[v-weight[i]]+c[i]

由此得到状态转移方程：f[v]表示重量不超过v公斤的最大价值
dp[v] = Math.max(dp[v],dp[v-n*w[i]] + n*c[i]) {0<n*value[i]<total}

//weight表示每件物品的重量，value代表每件物品的价值，total 表示容量，Num表示物品数量，设 f[v]表示重量不超过v公斤的最大价值
  public static int ZeroMorePackage(int []weight,int []value,int []dp,int Num,int total){
        for(int i = 0;i<Num;i++){
            for(int v = weight[i];v<=total;v++){ //注意是++
                dp[v] = Math.max(dp[v-weight[i]]+value[i],dp[v]);
            }
        }
        return dp[total];
    }

4.多重背包问题

有Num种物品和一个容量为total的背包。第i种物品最多有eachNum[i]件可用，每件体积是weight[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量total，且价值总和最大。

• 情况1：第i件不放进去，所得价值dp[v]
• 情况2：第i件放进去，所得价值dp[v-weight[i]] + c[i]

由此得到状态转移方程：dp[v]表示装入重量不超过v公斤的最大价值
  dp[v] = Math.max(dp[v] , dp[v-n*w[i]] + n*c[i]) {0 < k < eachNum[i]，0<k*value[i]<total}，

//多重背包问题
   public static int MorePackage(int []weight,int []value,int []dp,int Num,int total,int eachNum[]){
       for(int i = 0;i<Num;i++) {
           for (int v = total; v >= 0; v--) { //注意是逆序
               for (int k = 0; k <= eachNum[i]; k++) {
                   if (v - k * weight[i] < 0) {
                       break;
                   }else{
                       dp[v] = Math.max(dp[v - k * weight[i]] + k * value[i], dp[v]);
                   }
               }
           }
       }
       return dp[total];
   }

5.多限定条件的背包问题

   航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次.
输入格式
  第一行 两个数 体积最大值(<400)和质量最大值(<400)
  第二行 一个数 食品总数N(<50).
  第三行－第3+N行,每行三个数 体积(<400) 质量(<400) 所含卡路里(<500)
输出格式
   一个数,所能达到的最大卡路里(int范围内)
样例输入
   320  350
   4
  160  40  120
   80  110  240
   220 70   310
   40  400  220
样例输出
   550

dp[i][j][k]代表“前i件物品，此刻体积为j,质量为k时，可得到的最大卡路里值。

第i件不放进去，转化成前i-1件物品此刻体积为j,质量为k时，可得到的最大卡路里值，此时所得卡路里

       dp[i-1][j][k]

第i件放进去，要是体积只能为j,质量只能为k,则可以转化成将前i-1件物品放入体积为j-vol[i]，质量为k-qua[i]的背包里，此时加入第i件的体积恰好是j,质量恰好是k的背包，所得卡路里为

     dp[i-1][j-vol[i]][k-qua[i]]+ calorie[i]

由此得到状态转移方程：

   dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-vol[i]][k-qua[i]]+ calorie[i]);

可以将其压缩成空间为O(total) = O(N*N)

• 情况1：第i件不放进去，所得价值dp[j][k]
• 情况2：第i件放进去，所得价值dp[j-vol[i]][k-qua[i]]+ calorie[i]

由此得到状态转移方程：
       dp[j][k] = Math.max(dp[j][k],dp[j-vol[i]][k-qua[i]]+ calorie[i]);

> public class Main {
>     public static int  solution(int Num,int Volume,int Quality,int vol[],int qua[],int calorie[]){
>         int dp[][] = new int [Volume+1][Quality+1];
>         for(int i = 0;i<Num;i++){  //食品数量
>             for(int j = Volume;j>=vol[i];j--){  //体积
>                 for(int k = Quality;k >= qua[i];k--){ //质量
>                     dp[j][k] = Math.max(dp[j][k],dp[j-vol[i]][k-qua[i]]+ calorie[i]);
>                 }
>             }
>         }
>         return dp[Volume][Quality];
>     }
>     public static void main(String[] args) {
>         Scanner sr = new Scanner(System.in);
>         int Volume  = sr.nextInt();
>         int Quality = sr.nextInt();
>         int Num = sr.nextInt();
>         int vol[] = new int[Num];
>         int qua[] = new int[Num];
>         int calorie[] = new int[Num];
>         for(int i = 0;i<Num;i++){
>             vol[i] = sr.nextInt();
>             qua[i] = sr.nextInt();
>             calorie[i] = sr.nextInt();
>         }
>         System.out.println(solution(Num,Volume,Quality,vol,qua,calorie));
>     }
> }
>