首页 > 01背包 完全背包
头像
AB-IN
编辑于 2021-04-19 14:04
+ 关注

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
*/

完结。

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐