文章目录
- 01背包
- 一、01背包模板
- 二、采药
- 三、装箱问题
- 四、宠物小精灵之收服
- 五、数字组合
- 完全背包
- 六、完全背包模板
- 七、买书
- 八、货币系统（简单版）
- 九、货币系统（进阶版）
01背包
一、01背包模板
还有个疑惑，为什么最大价值一定是背包装满的时候？
因为你背包装满的情况囊括了前面不装满的情况
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N];
int n,m;
int v[N],w[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
for(int i = 1;i <= n;i ++)
for(int j = m;j >= v[i];j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
return 0;
}
二、采药
题目链接
这个题非常容易，套模板就行，把T当成体积，M当成物品个数
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 110;
int w[M], f[N], v[M];
int t, m;
int main()
{
scanf("%d%d", &t, &m);
for(int i = 1;i <= m;i ++) cin >> v[i] >> w[i] ;
for(int i = 1;i <= m;i ++)
for(int j = t;j >= v[i];j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[t];
return 0;
}
三、装箱问题
题目链接
这个题目也比较容易，我们之间把体积当成价值就行
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20010;
int f[N], v[N];
int n, V;
int main()
{
cin >> V >> n;
for(int i = 1;i <= n;i ++)
cin >> v[i];
//箱子的空间就是价值
for(int i = 1;i <= n;i ++)
for(int j = V;j >= v[i];j --)
f[j] = max(f[j], f[j - v[i]] + v[i]);
cout << V - f[V];
return 0;
}
四、宠物小精灵之收服
题目链接
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 510;
int f[N][M];
int V1[N], V2[M];
int n, m, k;
int main()
{
cin >> n >> m >> k;
for(int i = 1;i <= k;i ++) cin >> V1[i] >> V2[i];
for(int i = 1;i <= k;i ++)
for(int v1 = n;v1 >= V1[i];v1 --)
{
for(int v2 = m - 1;v2 >= V2[i];v2 --)
f[v1][v2] = max(f[v1][v2], f[v1 - V1[i]][v2 - V2[i]] + 1);
}
cout << f[n][m - 1] << ' ';
int t = m - 1;
while(t > 0 && f[n][t - 1] == f[n][t]) t --;
cout << m - t;
return 0;
}
五、数字组合
题目链接
这个题的难点在于初始化，你要求总和为M的方案数，而不是像上面的题目一样求从哪个状态过渡来的最大方案数，所以当你和为0的时候，你就要初始化此时方案数为1，因为你此时什么都不选也是一种方案
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
const int N = 10010;
int v[N];
int f[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> v[i];
f[0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = m;j >= v[i];j --)
f[j] += f[j - v[i]];//加上你从每个方案过渡来的情况
cout << f[m];
return 0;
}
完全背包
六、完全背包模板
题目链接
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i];
for(int i = 1;i <= n;i ++)
for(int j = v[i];j <= m;j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
}
七、买书
这个题也非常简单，就是套模板
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int a[5] = { 0,10,20,50,100};
int f[N];
int main()
{
cin >> n;
f[0] = 1;
for(int i = 1;i <= 4;i ++)
{
for(int j = a[i];j <= n;j ++)
f[j] += f[j - a[i]];
}
cout << f[n];
return 0;
}
八、货币系统（简单版）
题目链接
这里有一个坑，会int会暴栈
其他都是搓模板
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20, M = 3010;
typedef long long LL;
LL f[M];
int v[N];
int n,m;
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> v[i];
f[0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 0;j <= m;j ++)
if(j >= v[i])
f[j] += f[j - v[i]];
cout << f[m];
return 0;
}
九、货币系统（进阶版）
题目链接
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110, M = 25100;
int a[N],f[M];
int n;
int main()
{
int t;
cin >> t;
while(t --)
{
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
memset(f, 0, sizeof f);
f[0] = 1;//初始化当要表示0的和时候，0本身不能被丢掉,所以为真，被丢掉的元素为假
sort(a, a + n);//先排序找最大的元素，以这个元素为“标准体积”
int k = 0;
int m = a[n - 1];
for(int i = 0;i < n;i ++)
{
if(!f[a[i]]) k ++;//第一个数一定不能被表示出来
for(int j = a[i];j <= m;j ++)
f[j] |= f[j - a[i]];//一旦j这个和能够被前面的数表示出来，那么这个元素可以丢掉
}
cout << k << endl;
}
return 0;
}
