背包问题指一个给定容量的背包，若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。
背包问题又分为01背包和完全背包。

  1. 01背包：每个物品最多放一个，完全背包可以转换为01背包
  2. 完全背包：每种物品都有无限可用

背包问题分析

图表分析

现在有一个背包，容量为4磅，有如下图1这些物品。
要求达到的目标为装入的背包总价值最大，并且重量不超出，装入的物品不重复
image.png
我们可以用填表的方式来记录下每一步的决策。表里面装的是之前的物品能装进背包的总价值
如图2，当没有物品时（第二行），价值就是0。
当背包容量0磅时（第二列），一个东西都装不下，所以价值也是0.
image.png
当背包容量只有1磅时，遍历物品，看看谁能放进去，吉他可以，放了吉他，在放音响就放不下了，所以遍历到音响这里时，容量1磅的最大价值还是吉他，再遍历到了电脑，也放不下，所以到了电脑这里，容量1磅的最大价值还是吉他的价值1500。
同理。
当背包容量是3磅时，能放下吉他，然后放下不音响，所以遍历到了音响也只能放一个吉他价值1500，然后遍历到了电脑，能放下，就要比较价值了。电脑2000的价值，比遍历到音响时背包里面的价值都要多，就替换为2000作为3磅背包能放下最高的价值。

这里不是和吉他比较价值，是和当前物品之前背包里面的总价值比较，因为遍历到了音响还只放得下吉他，总价值就1500.

当背包容量是4磅时，正好遍历到了电脑，电脑3磅，能装进去就要试着去装一下，总共4磅-电脑3磅=1磅，剩余的这1磅，就在1磅的列里面找当前物品之前的能放入的物品最大价值，1500，电脑2000+之前1磅能放进去的最大价值1500=3500，而3500大于4磅时电脑之前的物品能放入的最大价值，所以3500替换为4磅时能放入的最大价值。
image.png

公式分析

背包问题利用动态规划来解决，每次遍历到第i个物品时，根据w[i](第i个物品的重量)和v[i](第i个物品的价值)，来确定是否需要将该物品放入背包中。
再令maxv[i][j]表示在前i个物品中能装入容量为j的背包中最大价值。
根据上面的图表分析，总结出规律：

  1. maxv[i][0]=maxv[0][j]=0
  2. 当w[i]>j时，v[i][j]=v[i-1][j]
  3. 当j>=w[i]时，v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+v[i])

代码

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Globalization;
  4. using System.IO;
  5. using System.Runtime.Serialization.Formatters.Binary;
  6. using System.Text;
  8. namespace ConsoleApp1
  9. {
  10.     class Program
  11.     {
  12.         static void Main(string[] args)
  13.         {
  14.             int[] w = { 1, 4, 3 };//物品的重量
  15.             int[] v = { 1500, 3000, 2000 };//物品的价值
  16.             int m = 4;//背包的容量
  17.             int n = v.Length;//物品的个数
  19.             //最大价值策略的二维数组，表示在前i个物品中能装入容器为j的背包中的最大价值
  20.             int[,] maxv = new int[n + 1, m + 1];//物品个数0-3，背包容量0-4
  21.             //为了记录放入商品的情况，我们定一个二维数组
  22.             int[,] path = new int[n + 1, m + 1];
  24.             //初始化第一行第一列（）
  25.             for(int i = 0; i < maxv.GetLength(0); i++)
  26.                 maxv[i, 0] = 0;//不管多少个物体，背包容量为0时都放不进入，价值永远为0
  27.             for (int j = 0; j < maxv.GetLength(1); j++)
  28.                 maxv[0, j] = 0;//不管背包容量为多少，没有物品放入，价值也是0
  30.             //根据前面的公式来动态规划
  31.             for(int i = 1; i < maxv.GetLength(0); i++)//不处理第一行了，因为第一行表示没有物体，都是0
  32.             {
  33.                 for(int j = 1; j < maxv.GetLength(1); j++)//不处理第一列
  34.                 {
  35.                     //公式
  36.                     if (w[i - 1] > j)//i是从1开始的，第一个物品的重量的下标是0
  37.                         maxv[i, j] = maxv[i - 1, j];
  38.                     else
  39.                     {
  40.                         //maxv[i, j] = Math.Max(maxv[i - 1, j], v[i - 1] + maxv[i - 1, j - w[i - 1]]);
  41.                         //为了记录商品存放到背包的情况，我们不能直接使用上买的简单公式，需要使用if-else
  42.                         if(maxv[i - 1, j]< v[i - 1] + maxv[i - 1, j - w[i - 1]])
  43.                         {
  44.                             maxv[i, j] = v[i - 1] + maxv[i - 1, j - w[i - 1]];
  45.                             //把当前的情况记录到path
  46.                             path[i, j] = 1;
  47.                         }
  48.                         else
  49.                         {
  50.                             maxv[i, j] = maxv[i - 1, j];
  51.                             //这里就不用记录了，因为path记录的是放入背包的物品，如果maxv[i - 1, j]是最大的，i这个物品没必要放
  52.                         }
  53.                     }
  54.                 }
  55.             }
  57.             //打印输出
  58.             for(int i =0;i<maxv.GetLength(0);i++)
  59.             {
  60.                 for(int j = 0; j < maxv.GetLength(1); j++)
  61.                     Console.Write(maxv[i,j]+" ");
  62.                 Console.WriteLine();
  63.             }
  65.             //打印哪些物品放入背包
  66.             int ii = maxv.GetLength(0)-1;
  67.             int jj = maxv.GetLength(1)-1;
  68.             while(ii > 0 && jj > 0)
  69.             {
  70.                 if (path[ii, jj] == 1)
  71.                 {
  72.                     Console.WriteLine($"第{ii}个商品放入背包");
  73.                     jj -= w[ii-1];//第ii个东西已经放入了背包，jj是当前背包的剩余容量，w[ii]表示已经放入物品的容量
  74.                 }
  75.                 ii--;//因为已经找到了一个，不能重复放，所以ii--，去找下一个
  76.             }
  77.         }
  79.     }
  80. }