P05: 二维费用的背包问题

P05: 二维费用的背包问题

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价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]范围内寻找答案。

http://www.cnphp6.com/archives/63014
和0-1背包类似，只不过限制条件多了一个体积而已，最简单的思路就是，多开一维数组控制这个条件。

for(i =1;i<n+1;i++)
   {
       cin>>w[i]>>b[i]>>v[i];
   }

   int dp[50][50][50]={0};        //dp[i][j][k] i代表着第1到第i个物品，j代表的是重量，k代表的是容积，dp为最优价值

   for(i=1;i<n+1;i++)
       for(j =1;j <=c;j++)
           for(k = 1 ;k <= d ; k++)
           {
               if(w[i]<=j&&b[i]<=k)  //当前物品重量小于当前容量，且体积小于容积时 ，才可以考虑装入物品的问题
                   dp[i][j][k] = max(dp[i-1][j][k] , dp[i-1][j-w[i]][k-b[i]] + v[i]);
               else dp[i][j][k] = dp[i-1][j][k];
           }
   cout<<“背包能放物品的最大价值为:”<<dp[n][c][d]<<endl;
  int x[MAX] ={0};   //记录是否被选中
  for(i =n;i>1;i–)
       if(dp[i][c][d]==dp[i-1][c][d])x[i] =0;
      else {x[i]=1;c -= w[i];d -= b[i];}
   x[1]=(dp[1][c][d])?1:0;
   cout<<“被选入背包的物品的编号,质量和体积,价值分别是:”<<endl;
   for(i=1;i<</span>n+1;i++)
       if(x[i]==1)
           cout<<“第”<<i<<“个物品: “<<w[i]<<”  “<<b[i]<<”  “<<v[i]<<endl;

复数域上的背包问题

另一种看待二维背包问题的思路是：将它看待成复数域上的背包问题。也就是说，背包的容量以及每件物品的费用都是一个复数。而常见的一维背包问题则是实数域上的背包问题。（注意：上面的话其实不严谨，因为事实上我们处理的都只是整数而已。）所以说，一维背包的种种思想方法，往往可以应用于二位背包问题的求解中，因为只是数域扩大了而已。

作为这种思想的练习，你可以尝试将P11中提到的"子集和问题"扩展到复数域（即二维），并试图用同样的复杂度解决。

Read full article from P05: 二维费用的背包问题