01背包

写在开头

有N件物品和一个容量为C的背包，第i件物品的费用是w[i],价值是v[i]，求在不超过背包的最大容量下，求能得到最大的价值

1. dp[i][j]表示前i件物品放入一个容量为j的背包可以获得的最大价值
2. 考虑第i件物品（放与不放）那么就有两种状态。
3. 如果不放，那么当前价值dp[i][j]=dp[i-1[[j-1],也就是和上一个状态相同的价值，因为我们并没有选择它放入背包，所以价值并没有变
4. 如果放入，那么我们就要减去这个物品的体积，并加上它的价值，我们在放与不放之间选取一个最大的dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - back[i].w] + back[i].v);
   转移方程出来了题目就解决了一大半
   
   

题目描述
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为C。如何选择装入背包的物品，可以使得装入背包中物品的总价值最大？
输入
每组输入包括三行，
第一行包括物品个数n，以及背包容量C。
第二、三行包括两个一维数组，分别为每一种物品的价值和重量。
输出
输出包括两行，第一行为背包的最大总价值，第二行为所选取的物品。
例如：最大总价值=15，物品选取策略为11001。
样例输入
5 10
6 3 5 4 6
2 2 6 5 4
样例输出
15
11001

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
const int minn = 1e3 + 10;
int dp[minn][minn];
int a[minn];
int n, m;
struct node //定义一个结构体来储存每个物品的消耗与价值
{
   
    int w, v;
} back[minn];
int ans()
{
   
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
        {
   
            if (back[i].w > j) //如果当前物品的消耗大于背包生于容量就不选
                dp[i][j] = dp[i - 1][j];
            else //否则就取一个最大值
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - back[i].w] + back[i].v);
        }
    return dp[n][m]; //返回最后的最大价值
}
int ans1()                      //逆序打表
{
                                  //当执行完上面的程序之后，我们已经走到了最后一步，所以要从最后一步开始往前推导
    for (int i = n; i > 1; --i) //防止溢出
        if (dp[i][m] == dp[i - 1][m])
            a[i] = 0;
        else
        {
   
            a[i] = 1;
            m = m - back[i].w;
        }
    a[1] = (dp[1][m] > 0 ? 1 : 0);
}
int main()
{
   
    while (~scanf("%d%d", &n, &m))
    {
   
        for (int i = 1; i <= n; ++i)
            scanf("%d", &back[i].v);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &back[i].w);
        printf("%d\n", ans());
        ans1();
        for (int i = 1; i <= n; ++i)
            printf("%d", a[i]);
        printf("\n");
    }
    return 0;
}

部分背包

• 部分背包的核心思想就是贪心选择策略。
• 部分背包与01背包最大的区别就是部分背包可以选择物品的一部分。
• 在部分背包中，我们优先选择单位消耗所产生的最大价值，也就是非常非常值钱的东西，只要我们能够装的下，我们就一直选择目前单位消耗产生最大价值的物品，直到背包装不下，也就是我们通常所说局部最优及全局最优
  AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
struct node
{
   
   double wi, vi;
   double pi;
   bool operator<(const node x) const
   {
   
      return pi > x.pi;
   }
} w[maxn];
int main()
{
   
   int n, c;
   while (~scanf("%d%d", &n, &c))
   {
   
      double ans = 0;
      for (int i = 1; i <= n; ++i)
         scanf("%lf", &w[i].vi);
      for (int i = 1; i <= n; ++i)
      {
   
         scanf("%lf", &w[i].wi);
         w[i].pi = w[i].vi / w[i].wi; //求出每个物品单位消耗所产生的价值，方便后续的贪心
      }
      sort(w + 1, w + n + 1);
      int i = 1;
      while (w[i].wi <= c && i <= n)//装的下就继续贪
      {
   
         ans += w[i].vi;
         c -= w[i].wi;
         ++i;
      }
      if (c > 0)//此时背包剩余容量小于当前物品的重量，那我们就取其中的一部分
      {
   
         double m = c / w[i].wi;
         ans += m * w[i].vi;
      }
      printf("%.2lf\n", ans);
   }
   return 0;
}