首页 > 代码库 > sdads
sdads
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有 一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和 b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
费用加了一维，只需状态也加一维即可。设f[v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是：
f[v][u]=max{f[i-1][v][u],f[v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。
到这里你也许也差不多有思路了，那么看下代码，应该能很好理解二维费用背包了
首先我们来看下完全背包的模板：
void CompletePack(int value,int weight)
{
int i;
for(i=weight;i<=V;i++)
dp[i]=max(dp[i],dp[i-weight]+value);
}
代码如下：
1 #include<stdio.h> 2 #include<string.h> 3 #define N 110 4 int dp[N][N];//二维的 5 int a[N],b[N]; 6 int max(int x,int y) 7 { 8 return x>y?x:y; 9 }10 int main()11 {12 int n,m,k,s,i,j,l;13 while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) //n为经验，m为忍耐度，k为怪的种数，s为最多杀的怪14 {15 for(i=0;i<k;i++)16 scanf("%d%d",&a[i],&b[i]); //得到的经验值和会减掉的忍耐度17 memset(dp,0,sizeof(dp));18 for(i=0;i<k;i++) //杀怪的循环 19 { 20 for(j=1;j<=s;j++) //限制条件，最多的杀怪数s21 {22 for(l=b[i];l<=m;l++) //二维背包问题的第二个for循环23 dp[j][l]=max(dp[j][l],dp[j-1][l-b[i]]+a[i]); //dp[j][l]它表示 用掉了l点的忍耐度，并且杀了j个怪后，所获得的最大经验数24 }25 }26 for(i=0;i<=m;i++) //i之所以从0开始到m是由于dp[j][l]它表示 用掉了l点的忍耐度，并且杀了j个怪后，所获得的最大经验数27 if(dp[s][i]>=n) break; //即用掉了m点的忍耐度，并且杀了s只怪兽后,所获得的最大经验数28 if(dp[s][i]<n) //break即跳出后还小于升级所需经验值时。。。 29 printf("-1\n"); //即如果在杀掉s只怪兽后所得的经验值小于还需要的经验值的话就无法升级输出-1 30 else31 printf("%d\n",m-i); ////在杀了s只怪兽后，用掉了i大小的忍耐度，则还能保留的最大忍耐度是m-i32 }33 return 0;34 } 35
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。