01背包完全背包

~~我太菜了，现在才学~~

一、01背包

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

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

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

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

什么意思呢？

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

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

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

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

01滚动。顾名思义，就是两行之间的相互利用。 $d p [0 / 1] [j]$ 一行记录前一行的值，另一行记录当前行的值。
就地滚动。顾名思义，就是用一个一维数组，之前的状态和当前的状态都在同一个数组里。

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

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

那该怎么办呢？

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

代码孕育而生。

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

二、完全背包

$n$ 是物品的个数， $v$ 是背包的容量，每种物品都有无限件可用， $c [i]$ 代表第 $i$ 物品的费用， $w [i]$ 代表第 $i$ 物品的价值。

在讲就地滚动的时候，如果 $j$ 从 $c [i]$ 到 $v$ 的话，会出现 $b u g$ ，一个物品会被算多次，这不恰好是我们想要的吗？

所以

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

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

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

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

$d p$ 数组的定义上,都变成 $i n f$ 。 $d p [0] = 0$ 。
核心代码
```
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];
}
```
如果这里用大于号的话，那么一直取最小的硬币即可，因为每个硬币的 $w$ 都为1。所以这里不应该用大于号，应该用 $\le$ 。

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

另外就是背包路径记录。用链表记录即可。用 $j$ 指向上一个 $j - f [i]$ 。

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