0-1背包之一
n个重量价值分别为wi，vi的物品。从这些物品中挑选出总重量不超过W的物品，求价值总和的最大值。
限制条件{n(1,100)、wi,vi(1,100)、W(1,1000)}
枚举+dfs：
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100;
int w[MAXN],v[MAXN];
int n;
int solve(int i,int j)
{
int re;
if(i==n)
re=0;
else if(j<w[i])
re=solve(i+1,j);
else
re=max(solve(i+1,j),solve(i+1,j-w[i])+v[i]);
return re;
}
int main()
{
int i,W;
scanf("%d%d",&n,&W);
for(i=0;i<n;i++)
scanf("%d%d",w[i],v[i]);
printf("%d
",solve(0,W));
return 0;
}
由于dfs会出现很多重复计算的情况；
剪枝后；
int dp[MAXN][MAXN];
int solve(int i,int j)
{
int re;
if(dp[i][j])
re = dp[i][j];
else if(i==n)
re = 0;
else if(j<w[i])
re = solve(i+1,j);
else
re = max(solve(i+1,j),solve(i+1,j-w[i])+v[i]);
return re=dp[i][j];
}动态规划
递推1：dp[i][j]表示考虑第i个物品后w用j的最优挑选方案
dp[n][j]=0；
当j<w[j]时，dp[i][j]=dp[i+1][j]；
其它，dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])；
int dp[MAXN][MAXN_W];
int solve()
{
for(int i=n-1;i>=0;i--)
for(int j=0;j<=w;j++)
if(j<w[i])
dp[i][j]=dp[i+1][j];
else
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[j]);
return dp[0][w];
}递推2：dp[i+1][j]表示从前i个物品中选出总重量不超过j的物品时总价值的最大值
dp[0][j]=0；
当j<w[i]时，dp[i+1][j]=dp[i][j]；
其它情况，dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])；
int solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<=w;j++)
if(j<w[i])
dp[i+1][j]=dp[i][j];
else
dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
return dp[n][w];
}状态转移：“前 i 个物品中挑选总重量不超过 j 时的状态” 向 “前 i+1 个物品中选取总重不超过 j ” 和 “前 j+1 个物品中选取总重不超过 j+w[i] 时的状态” 转移。
void solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<=w;j++)
{
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+w[i]<=W)
dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
}
return dp[n][W];
}完全背包
有n种重量和价值分别为wi，vi的物体。从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值。
限制条件：{ n[1,100] 、wi,vi[1,1000]、W[1,10000]) }
dp[i+1][j]表示从前 i 种物品中挑选总重量不超过 j 时总价值的最大值。
dp[0][j]=0；
dp[i+1][j] = max{ dp[ i-k*w[i]]+k*v[i] | 0<=k }；
int dp[MAXN][MAXN];
int solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
for(int k=0;k*w[i]<=j;k++)
dp[i+1][j] = max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
return dp[n][w];
}上面的程序三层循环。其实在计算每一行的结果的时候都重复计算了，j=j`+w[i]，在dp[i][j`] 计算dp[i][j`-k*w[i]]+k*v[i]后，会计算dp[i][j-k`*w[i]]+k`*v[i]，而当k=k`-1前面的计算就是和后面的计算是一样的。也就是当k>0的时候的计算都是重复计算。
dp[i+1][j] = max{ dp[i][j-k*w[i]]+k*v[i] | 0<=k }
= max( dp[i][j],max{ dp[i][j-k*w[i]]+k*v[i] | 1<=k )
= max( dp[i][j],max{ dp[i][(j-w[i])-k*w[i]]+k*v[i] | 0<=k }+v[i])
= max( dp[i][j],dp[i+1][j-w[i]]+v[i])#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=101;
int dp[MAXN][MAXN];
int v[MAXN],w[MAXN];
int n,W;
int solve()
{
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
if(j<w[i])
dp[i+1][j]=dp[i][j];
else
dp[i+1][j]=max( dp[i][j],dp[i+1][j-w[i]]+v[i] );
return dp[n][W];
}
int main()
{
scanf("%d%d",&n,&W);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);
printf("%d
",solve());
return 0;
}使用一维数组实现0-1背包和完全背包
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=101;
int dp[MAXN];
int w[MAXN],v[MAXN];
int n,W;
int solve_01()
{
for(int i=0;i<n;i++)
for(int j=W;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[W];
}
int solve_com()
{
for(int i=0;i<n;i++)
for(int j=w[i];j<=W;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[W];
}
int main()
{
scanf("%d%d",&n,&W);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);
char op[10];
scanf("%s",op);
if(op[0]=='0')
printf("%d
",solve_01());
else
printf("%d
",solve_com());
return 0;
}
0-1背包之二
有n个重量和价值分别为wi,vi的物品。从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和最大值。
限制条件：{ n[1,n]、wi[1,1e7]、vi[1,100]、W[1,1e9] }；
因为限制条件的变化，如果方法不变的话dp数组中的j最大为1e9，内存是超级大的，因此可以试着改变DP的对象。之前的方法中，是真多重量，这里不妨针对价值计算最小的重量。
dp[i+1][j]表示前i个物品中挑选出价值总和为j时总重量的最小值（不存在时就是一个充分大的数值INF）。
dp[0][0]=0；
dp[0][j]=INF；
dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i])；
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100,MAXV=100,INF=1e9+1;
int dp[MAXN+1][MANX*MANV+1];
int w[MAXN],v[MAXN];
int n,W;
int solve()
{
fill(dp[0],dp[0]+MAXN*MAXV+1,INF);
dp[0][0]=0;
for(int i=0;i<n;i++)
for(int j=0;j<=MAXN*MAXV;j++)
if(j<v[i])
dp[i+1][j]=dp[i][j];
else
dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
int re=0;
for(int i=0;i<=MAXN*MAXV;i++)
if(dp[n][i]<=W)
re = i;
return re;
}
int main()
{
scanf("%d%d",&n,&W);
for(int i=0;i<n;i++)
scanf("%d%d",&w[i],&v[i]);
printf("%d
",solve());
return 0;
}多重背包
有n种不同大小的数组ai，每种各mi个。判断是否可以从这些数组之中选出若干使他们的和恰好为k。
限制条件{ n[1,100]、ai,mi[1,100000]、k[1,100000] }
dp[i+1][j]表示前i种数加和得到j时第i种数最多能剩余多少个（不能加和得到i的情况下为-1）
dp[i][j]>=0时，dp[i+1][j]=m[i]；
j<a[i]或者dp[i+1][j-a[i]]<=0时，dp[i+1][j]=-1；
其它情况，dp[i+1][j]=dp[i+1][j-a[i]]-1；
#include<cstdio>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=1e5+1;
int a[MAXN],m[MAXN];
int dp[MAXN];
int n,k;
void solve()
{
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=0;i<n;i++)
for(int j=0;j<=k;j++)
if(dp[j]>=0)
dp[j]=m[i];
else if(j<a[i]||dp[j-a[i]]<=0)
dp[j]=-1;
else
dp[j]=dp[j-a[i]]-1;
if(dp[k]>=0)printf("Yes
");
else printf("No
");
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",a[i]);
for(int i=0;i<n;i++)
scanf("%d",m[i]);
solve();
return 0;
}