关于01背包问题

  关于伟大的DP,入门便是从背包问题开始,没错，背包分为01背包,完全背包,多重背包等。
  众所周知完全背包便是01背包的反向思想,那么什么是01背包?没错01背包,顾名思义0和1(废话)，就是选(1)和不选(0)。
  有一大堆东西(n件),有价值(v),有重量(w),有一个承重(V)的背包，嗯没错,跟贪心差不多，求可以装到的西的价值之和最大。
  现在定义f数组,f[i]表示重量为i的背包(数组下标)能装到的最大价值，那么我们要求的答案就是f[V]。
  为何如此定义?
  因为动归的思想就是从子问题(小问题)下手，解决子问题再解决大一点的子问题,解决大一点的子问题,就解决更大的子问题从而解决整个问题。
  好比写文章，你得先学拼音，再习识字，再学习写字，再学习构思，再开始写文章。
  如何求f[i]呢?我们不妨枚举每一个物品。
  嗯,那么第一个for就出来了。

  for(int i=1;i<=n;i++)

  嗯，真香。
  然后呢枚举能装下这个物品的全部背包。

  for(int j=V;j>=v[i];j--)

  嗯,然后计算背包能装下的物品的最大价值之和。

  f[j]=max(f[j],f[j-w[i]]+v[i]);

  顾名思义前者,f[j]就是不选这个东西。
  后者f[j-w[i]]+v[i]便是选这个东西，+v[i]众所周知选这个物品就要加上他的价值。
  那么j-w[i]是何意义呢?
  嗯没错j指重量j,w[i]指这个物品的重量。
  在当前情况下我们不知道背包够不够装这个物品，所以我们必须要腾出w[i]的空间来装这个物品。
  那么f[j-w[i]]在这里表示的是，我腾出空间(丢掉一些东西）时可获得的最大价值。
  所以核心部分便是:

 for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
      f[j]=max(f[j],f[j-w[i]]+v[i]);

  然后呢

 printf("%d\n",f[V]);

  大功告成！

关于01背包问题

原文：https://www.cnblogs.com/BiuBiu-Miku/p/12249079.html