二维费用背包

①基本题型：二维费用的背包问题是指对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大

值（背包容量），求选择物品可以得到最大的价值。设第i件物品所需的两种代价分别为v[i]和u[i]，两种代价可付出的最大值（两种背包容量）分

别为V和U，物品的价值为w[i]。

②基本解法：相比经典的01背包问题，二维费用背包问题增加了一维费用，于是我们需要在状态上增加一维。设s[i][j][k]表示将前i件物品放入两种容量

分别为j和k的背包时所能获得的最大价值，则状态转移方程为s[i][j][k]=max{s[i-1][j][k], s[i-1][j-v[i]][k-u[i]]+w[i]}，递推边界为当i=0时

s[i][j][k]=0。和01背包类似，状态的维数可以轻易的从三维降低到二维，具体实现见代码。

dp.二维费用背包

memset(dp,0,sizeof(dp)) // 初始化边界

for (int i=1; i<=N; i++)
{
      for (int j=V; j>=v[i]; j--)
      {
            for (int k=U; k>=u[i]; k--) s[j][k]=max(s[j][k], s[j-v[i]][k-u[i]]+w[i]);
      }
}

总结：由二维费用背包问题我们可以推知多维费用背包其实就是增加状态维数，其他类型的DP问题如果是通过原型问题增加限制条件改编而来，应该也可以通过类似的增加状态维数来解决。

二维费用背包基础

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

最近xhd正在玩一款叫做FATE的游戏，为了得到*装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

Input

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

Output

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

Sample Input

        10 10 1 10 1 1 10 10 1 9 1 1 9 10 2 10 1 1 2 2 
      

Sample Output

        0 -1 1 
      

此题就地滚动，用二维，求出背包最后的剩余空间量，重点要找到几个维度的费用都指的是啥。

c++,dp,二维费用背包

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,k,s;
int a[105],b[105];
int dp[105][105];//忍耐度，刷怪数

void solve()
{
	for(int i=0;i<k;i++)
		scanf("%d%d",&a[i],&b[i]);
		memset(dp,0,sizeof(dp));

	int min_=m+1;
	for(int i=0;i<k;i++)
		for(int j=b[i];j<=m;j++)
			for(int k=1;k<=s;k++)
	        {
              dp[j][k]=max(dp[j][k],dp[j-b[i]][k-1]+a[i]);
		     if (dp[j][k] >= n) min_=min(min_,j);
	        }
	if (min_ == m + 1) printf("-1\n");
	else printf("%d\n", m - min_);
}



int main()
{
   while(~scanf("%d%d%d%d",&n,&m,&k,&s))
	solve();
    return 0;
}

秒客网

二维费用背包

相关文章