Powered by:AB_IN 局外人

我太菜了，现在才学

看的入门班的录播，大约明白了。

n n n是物品的个数， v v v是背包的容量， c [ i ] c[i] c[i]代表第 i i i物品的费用， w [ i ] w[i] w[i]代表第 i i i物品的价值。

先给出最原始推出来的式子

dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

什么意思呢？

d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i件物品恰好放入一个容量为 j j j的背包里可以获得的最大价值。

• d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]就表示，不选第 i i i个物品，就让前 i − 1 i-1 i−1个物品去组成容量为 j j j的背包。
• d p [ i − 1 ] [ j − c [ i ] ] dp[i-1][j-c[i]] dp[i−1][j−c[i]]就表示，选第 i i i个物品，让 j − c [ i ] j-c[i] j−c[i]的背包正好加上第 i i i个物品，容量不就正好为 j j j了嘛。
• 这两个取最大值即可。

但问题是这样太浪费空间了，可以通过式子看出 d p [ i ] [ ] dp[i][] dp[i][]只和 d p [ i − 1 ] [ ] dp[i-1][] dp[i−1][]有关，也就是和上一行。再加上 i i i是从 1 1 1到 n n n的，也就是前面一些行就没有用了，会很浪费空间。

所以便有了01滚动和就地滚动。

• 01滚动。顾名思义，就是两行之间的相互利用。 d p [ 0 / 1 ] [ j ] dp[0/1][j] dp[0/1][j]一行记录前一行的值，另一行记录当前行的值。

• 就地滚动。顾名思义，就是用一个一维数组，之前的状态和当前的状态都在同一个数组里。

  但如果 j j j从 c [ i ] c[i] c[i]到 v v v的话，会出现 b u g bug bug，一个物品会被算多次，因为 j j j会一直往右走到 v v v。比如一个放进去了， j j j往右走，会走到刚刚放进去的那个状态，原先放进去的会被再放一遍，显然这样是错的，因为上一行状态和这一行状态混了。

  那该怎么办呢？

  让 j j j从右往左走即可。上一行的状态在 j j j的左边，这一行的状态在 j j j的右边。

  代码孕育而生。

	for(int i=1;i<=n;i++){ 
        for(int j=v;j>=c[i];j--){ 
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }

爱玩游戏的Tom

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
typedef long long ll;
ll n,m,dp[N],c[N],w[N];
int main()
{ 
    cin>>n>>m;
    for(ll i=1;i<=n;i++){ 
        cin>>c[i]>>w[i];
    }
    for(ll i=1;i<=n;i++){ 
        for(ll j=m;j>=c[i];j--){ 
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

小梁的背包

#include<bits/stdc++.h>
#include<unordered_map>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i,a,n) for (rint i=a;i<n;i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i,a,n) for (rint i=a;i>n;i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
const int inf=0x3f3f3f3f;

namespace IO{ 
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){ 
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){ 
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline ll read(){ 
        register ll x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){ 
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{ 
    public:
        ~flusher_(){ if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;
const int N=1e4+10;
ll t,n,s,w[N],v[N],dp[N],num[N];
int main()
{ 
	t=read();
    while(t--){ 
        n=read();s=read();
        mset(dp, 0);
        mset(num, 0);
        rep(i, 1, n) v[i]=read(),w[i]=read();
        rep(i, 1, n){ 
            per(j, s, v[i]){ 
                //判断数量在前！
                if(dp[j-v[i]]+w[i]>dp[j]) num[j]=num[j-v[i]]+1;
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        write(dp[s]);pc(' ');write(num[s]);
        pc('\n');
    }
	return 0;
}

完结。