背包九讲----二维费用背包
问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
算法
费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
物品总个数的限制
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
对于01背包，完全背包，及由01背包和完全背包组成的多重背包不太清楚可以看看背包九讲
dp[i][jj]代表的意思是花费i的忍耐值杀了jj只怪所获得的经验值
这道题符合完全背包，下面的两种解法就是完全背包的两种解法
这道题基于O(VN)算法的解法代码：
for(int jj=1;jj<=s;jj++)加了一个杀怪数的约束，这道题每种怪的杀怪数并不是无限的，只是未知的,这就是上面说的另一个费用
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int dp[][];
const int inf=1e9;
struct Moster
{
int per;
int end;
}moster[];
int main()
{
int p, n,m,k,s,i,j,a,b;
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{
p=;int ans=inf;
memset(dp,,sizeof(dp));
for(i=;i<k;i++)
scanf("%d%d",&moster[i].per,&moster[i].end);
for(i=;i<k;i++)
{
for(j=moster[i].end;j<=m;j++)
{
for(int jj=;jj<=s;jj++)
{
dp[j][jj]=max(dp[j][jj],dp[j-moster[i].end][jj-]+moster[i].per);
if(dp[j][jj]>=n&&j<ans)
{
ans=j;
}
}
}
}
if(ans==inf)
printf("-1\n");
else
printf("%d\n",m-ans);
}
return ;
}
基于状态转移方程 f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}的解法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int dp[][];
const int inf=1e9;
struct Moster
{
int per;
int end;
}moster[];
int main()
{
int p, n,m,k,s,i,j,a,b;
while(~scanf("%d%d%d%d",&n,&m,&k,&s))
{
p=;int ans=inf;
memset(dp,,sizeof(dp));
for(i=;i<k;i++)
scanf("%d%d",&moster[i].per,&moster[i].end);
for(i=;i<=m;i++)
{
for(j=;j<k;j++)
for(int jj=;jj<=s;jj++)
{
int ant=;
while((i>=moster[j].end*ant)&&ant<=jj)
{
ant++;
dp[i][jj]=max(dp[i][jj],dp[i-moster[j].end][jj-]+moster[j].per);
}
}
if(dp[i][s]>=n)
{
ans=i;break;
}
}
if(ans==inf)
printf("-1\n");
else
printf("%d\n",m-ans);
}
return ;
}
if(dp[i][s]>=n)
{
ans=i;break; }
花费i的忍耐值杀了s值怪后获得的经验值满足升级所需的经验值就跳出循环
花费忍耐值就是最低的，题目只要求花费忍耐值最低，并不要求杀怪数（当然是最大杀怪数满足题目的要求下）