【解题报告】01背包

这应该是最基础的背包问题了，但正因为他的基础，他的思想会被用在很多DP题中，所以这里有必要对他剖析一下。

我们应该掌握的方法有两种

1、二维数组。
2、滚动数组。

后面那个一看就要高级一些，但是确实对动归没有太大的帮助，所以大家一定要把第一种方法学好！第二种方法我不做解释，只会黏贴代码，大家认真脑补一下应该也是可以理解的。

题目链接：
01背包问题

二维数组法：

这里定义背包叫做f[i][j],i代表前i个物品的总重为j，f[i][j]一起表示前i个物品的总共价值，所以我们就可以很明显的写出动态转移方程式：

 if(w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
    else f[i][v]=f[i-1][v];//important

然后大家应该都懂了，至于有些人问为什么中间看着这么别扭不直接这样写：

if(w[i]<=v) f[i+1][v+w[i]]=max(f[i][v]+c[i],f[i+1][v+w[i]]);
······ 

这当然是有原因的，是因为害怕一直往后扔会出现重复的情况！！！

下面上代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int m,n;
int w[35],c[35];
int f[35][205];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1;i<=n;++i)
    {
        for(int v=m;v>0;--v)
        {
            if(w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
            else f[i][v]=f[i-1][v];//important
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

P.s：中间加important的地方一定不要漏写了！

滚动数组法：

直接贴代码，大家脑补吧！

#include<cstdio>
#include<cstring>
using namespace std;
int bag[305];
int m,n;
int main()
{
    scanf("%d%d",&m,&n);
    int a,b;
    int limit=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&a,&b);
        for(int j=limit;j>=0;--j)
        {
            if(bag[j]!=0||(j==0))
            {
                if(bag[j+a]<bag[j]+b&&j+a<=m)
                {
                    bag[j+a]=bag[j]+b;
                }
                if(limit<j+a)
                limit=j+a;
            }
        }
    }
    int ans=-1;
    for(int i=0;i<=m;++i)
    {
        if(bag[i]>ans)
        ans=bag[i];
    }
    printf("%d",ans);
    return 0;
}

上面写假了！

/*
    Name: P1048 采药
    Copyright: njc
    Author: Mudrobot
    Date: 2018/10/19 10:56:23
    Description: Dynamic Programming
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 1004
using namespace std;
/*inline char gc() {
  static char buf[1<<18],*fs,*ft;
  return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
  register int k=0,f=1;
  register char c=gc();
  for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
  for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
  aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int dp[N],w[N],val[N],n,t;
int main()
{
    //freopen(".in", "r", stdin);freopen(".out", "w", stdout);
    scanf("%d%d",&t,&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&w[i],&val[i]);
    for(int i=1;i<=n;++i){
        for(int j=t;j>=0;--j){
            if(j>=w[i])dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
        }
    }
    printf("%d",dp[t]);
    //fclose(stdin);fclose(stdout);
    return 0;
}
/*
70 3
71 100
69 1
1 2
*/

谢谢采纳！