背包问题
应用场景
给定 $n$ 种物品和一个背包。物品 $i$ 的重量是 $w_i$ ，其价值为 $v_i$ ，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包的总价值最大？
*01 背包
*01 背包特点：
给定 $n$ 种物品和一个背包 ( 每个物品只能选取一个)。物品$i$ 的重量是$w[i]$，其价值为$v[i]$，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？
*状态：
$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值。
*限制条件
• 只能选择物品 1 ~ i
• 选择物品的总重量不能超过 $j$
*状态转移方程：
$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$;
*实现：
1）初始化：
int n,m; //n表示物品个数，m表示背包容量
for (int i = ;i<= m ;i++)
dp[][i] = ;
2）-1二维数组实现：
for (int i = ;i <= n ;i++){
for (int j = ;j<=m ;j++){
dp[i][j] = dp[i-][j];
if (j-w[i]>=)
dp[i][j] = max(dp[i][j],dp[i-][j-w[i]]+v[i]);
}
}
2）-2一维数组实现
for (int i = ;i <= n ;i++){
for (int j = m ;j>= ;j--){
if (j-w[i]>=)
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
*完全背包
*完全背包特点
给定 $n$ 种物品和一个背包 ( 每个物品选取无限个)。物品 $i$ 的重量是 $w[i]$,其价值为$v[i]$，背包的容量为$C$。应该如何选择装入背包的物品，是的装入背包中物品的总价值最大？
*状态
$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值。
*限制条件
• 只能选择物品 1 ~ i
• 选择物品的总重量不能超过 j
*状态转移方程
$dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])$;
*实现
1）初始化
int n,m; //n表示物品个数，m表示背包容量
for (int i = ;i<= m ;i++)
dp[][i] = ;
2）-1二维数组实现
for (int i =;i <= n;i++){
for (int j = ;j <= m;j++){
dp[i][j]=dp[i-][j];
if (w[i]<=j)
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
2）-2一维数组实现
for (int i =;i <= n;i++){
for (int j = ;j <= m;j++){
if (d-w[i]>=)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
*多重背包
*多重背包特点
给定 $n$ 种物品和一个背包 ( 每个物品选取有限个)。物品 $i$ 的重量是 $w[i]$ ，其价值为$v[i]$，每个物品可以取$k[i]$个，背包的容量为C。应该如何选择装入背包中的物品使得装入背包中的物品总价值最大？
*状态
$dp[i][j]$ 表示在只能从 $1-i$ 个物品中选择物品并且背包容量大小为 $j$ 的情况下，所能获得的最大价值
*限制条件
• 只能选择物品 1 ~ i
• 选择物品的总重量不能超过 j
*状态转移
$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i], dp[i-1][j-w[i]*2] + v[i]*2,...)$
*实现
1）初始化
2）-1二维数组实现
for (int i = ;i <= n ;i++){
for (int j = ;j<=m ;j++){
dp[i][j] = dp[i-][j];
for (int z = ; z<=k[i]; z++)
if (j-w[i]*z>=)
dp[i][j] = max(dp[i][j],dp[i-][j-z*w[i]]+z*v[i]);
else
break;
}
}
2）-2一维数组实现
for (int i = ;i <= n ;i++){
for (int j = m ;j>= ;j--){
for (int z = ; z<=k[i] ;z++)
if (j-w[i]*z>=)
dp[j] = max(dp[j],dp[j-z*w[i]]+z*v[i]);
else
break;
}
}
*多重背包问题转化为 01 背包问题
1. p 以下的数字可否由若干不同数字通过组合得到
(a) $2^n$- 1 $n$ == 7 二进制: 111111 000001、000010、000100、001000、010000、100000
(b) $k$ + $2^n$ -1 < $2^{n+1}$ -1 $n$ == 7
• $2^n$ -1 及以下的数字可以由以下数字表示 000001、000010、000100、001000、010000、100000
• 大于 $2^n$ -1 的数字 $k$ 加上以上 7 个数字组成的数字可以表示任何大于$2^n$ - 1小于等于k+$2^n$-1的数字
2. 代码实现
//num[i] 表示第i种硬币可以取多少次
//w[j] 表示转后为01背包后 只能取一次的硬币的价值与重量
int totlW = ;
memset(w,,sizeof w);
for (int i = ;i< ; i ++){
for(int j=; j<=num[i]; j<<=){
w[totlW++]=j*(i+);
num[i]-=j;
}
if(num[i]>)
w[totlW++]=num[i]*(i+);
}
背包问题
HDU 2602
POJ 2063
POJ 1787
UVA 674
UVA 147
第一题是01背包的板子题，就直接放代码了：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int t;
int n,m;
int val[],w[],f[];
int main ()
{
scanf ("%d",&t);
while (t--)
{
scanf ("%d%d",&n,&m);
memset(f,,sizeof(f));
for (int i = ;i <= n;i++)
scanf ("%d",&val[i]);
for (int i = ;i <= n;i++)
scanf ("%d",&w[i]);
for (int i = ;i <= n;i++)
for (int j = m;j >= w[i];j--)
f[j]=max(f[j],f[j-w[i]]+val[i]);
printf ("%d\n",f[m]);
}
return ;
}
第二道题是完全背包，因为每个债券都是1000的倍数，所以我们可以直接把总钱数和债券的数额都直接除以1000.因为每年都会有利息，所以每年的总钱数会增加，求出每一年的最大利益，总钱数加上最大利益就是下一年的总钱数。所以，我们只需要对于每一年的总钱数求一个完全背包，每年更新总钱数就好。代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = ;
int dp[N];
int num[N], val[N];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int money,year,d;
scanf("%d %d", &money, &year);
scanf("%d", &d);
for(int i=;i<d;i++)
{
scanf("%d %d", &num[i], &val[i]);
num[i]/=;
}
int sum=money;
for(int i=;i<year;i++)
{
memset(dp,,sizeof(dp));
money=sum;
money/=;
for(int j=;j<d;j++)
{
for(int k=num[j];k<=money;k++)
{
dp[k]=max(dp[k-num[j]]+val[j],dp[k]);
}
}
sum+=dp[money];
}
printf("%d\n",sum);
}
return ;
}
第三题是完全背包+路径输出，$dp[j]$表示总价格为$j$时最多可以有多少个硬币，但是需要维护一下硬币的个数，实际上在01背包中，我们对所有状态都更新了一次答案，这里我们等于是对4种硬币各跑一次背包，维护一下使用次数即可。$used[j]$表示总价格为j时用了多少个某个硬币。$pre[j]$记录方案，表示j出现更有的答案时是由哪个状态转移来的。最后遍历一下输出答案就好了。
#include <stdio.h>
#include <string.h>
using namespace std;
int dp[], used[], pre[], coin[] = {, , , }, num[], ans[];
int main(){
int p;
while(scanf("%d %d %d %d %d", &p, &num[], &num[], &num[], &num[]) != EOF){
if(p + num[] + num[] + num[] + num[] == ) return ;
for(int i = ; i <= p; ++i){
dp[i] = -1e9;
}
memset(pre, , sizeof(pre));
pre[] = -;
dp[] = ;
for(int i = ; i < ; ++i){
memset(used, , sizeof(used));
for(int j = coin[i]; j <= p; ++j){
if(dp[j] < dp[j - coin[i]] + && used[j - coin[i]] < num[i]){
used[j] = used[j - coin[i]] + ;
dp[j] = dp[j - coin[i]] + ;
pre[j] = j - coin[i];
}
}
}
if(dp[p] <= ){
printf("Charlie cannot buy coffee.\n");
continue;
}
memset(ans, , sizeof(ans));
while(){
if(pre[p] == -) break;
ans[p - pre[p]]++;
p = pre[p];
}
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[], ans[], ans[], ans[]);
}
}
第四题一个简单的动态规划，比如要求55的组成方案数，必须要知道55-1=54的方案数 和 55-5=50的方案数，和50-10=45的方案数和55-25=30的方案数和55-50=5的方案数，所以dp以此类推，每次更新dp。
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
int f[];
int main ()
{
int v;
while(cin>>v){
memset(f,,sizeof(f));
int c[]={,,,,,};
f[]=;
for(int i = ; i <= ; ++i)
for(int j = c[i]; j <= v; ++j)
{
f[j] = f[j]+f[j-c[i]];
}
cout << f[v]<<endl;
}
return ;
}