01背包 完全背包

Powered by:AB_IN 局外人

我太菜了，现在才学

一、01背包

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

是物品的个数，是背包的容量，代表第物品的费用，代表第物品的价值。

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

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

什么意思呢？

表示**前件物品恰好放入一个容量为的背包**里可以获得的最大价值。

• 就表示，不选第个物品，就让前个物品去组成容量为的背包。
• 就表示，选第个物品，让的背包正好加上第个物品，容量不就正好为了嘛。
• 这两个取最大值即可。

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

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

• 01滚动。顾名思义，就是两行之间的相互利用。一行记录前一行的值，另一行记录当前行的值。
• 就地滚动。顾名思义，就是用一个一维数组，之前的状态和当前的状态都在同一个数组里。

显然就地滚动更佳，因为只用一维数组。

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

那该怎么办呢？

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

代码孕育而生。

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>
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]=dp[j-v[i]]+w[i];
                }
            }
        }
        write(dp[s]);pc(' ');write(num[s]);
        pc('\n');
    }
    return 0;
}

二、完全背包

是物品的个数，是背包的容量，每种物品都有无限件可用，代表第物品的费用，代表第物品的价值。

在讲就地滚动的时候，如果从到的话，会出现，一个物品会被算多次，这不恰好是我们想要的吗？

所以

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

Optimal Coin Change

这个题不能按照上面的板子直接套。

首先先看题面，是让我们把拆成题目给的尽可能少的硬币，如果可能的解决方案不止一种，则应输出使用更多面值较低的硬币的解决方案 。

这里的价值就是1，而这里我们要的是装满背包最少的价值，所以在数组的定义上，还有转移方程的判定条件上会有改动。

• 数组的定义上,都变成。。

• 核心代码

    if (dp[j - f[i]] < inf && dp[j - f[i]] + 1 <= dp[j]) {
         dp[j] = dp[j - f[i]] + 1;
         pre[j] = j - f[i];
    }

  如果这里用大于号的话，那么一直取最小的硬币即可，因为每个硬币的都为1。所以这里不应该用大于号，应该用 。

  那为什么用呢？因为如果要数量少，还得往后递推，用较大面值补上一些多余的小面值钱数。

  另外就是背包路径记录。用链表记录即可。用指向上一个。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
int v, n, f[12], dp[N], pre[N], a[N];
int main() {
    while (~scanf("%d%d", &v, &n)) {
        memset(dp, 0x3f, sizeof(dp));
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            scanf("%d", &f[i]);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = f[i]; j <= v; j++) {
                if (dp[j - f[i]] < inf && dp[j - f[i]] + 1 <= dp[j]) {
                    dp[j] = dp[j - f[i]] + 1;
                    pre[j] = j - f[i];
                }
            }
        }
        if (dp[v] == inf)
            puts("-1");
        else {
            while (v) {
                a[v - pre[v]]++;
                v = pre[v];
            }
            for(int i=1;i<=n;i++){
                printf("%d ",a[f[i]]);
            }
            printf("\n");
        }
    }
    return 0;
}
/*
2000 7 10 20 50 100 200 500 1000
250 4 10 20 125 150
35 4 10 20 125 150
48 4 1 8 16 20
40 4 1 10 13 37
43 5 1 2 21 40 80
*/

完结。