描述

有n种物品和一个容积为V的背包，第i种物品有amount[i]个，体积cost[i]和价值valum[i]，问如何选取物品使得放入背包的物品价值之和最大。

思路

跟完全背包问题类似，这里就直接给出基本算法的状态转移方程 $dp[i][j]=Max\{dp[i-1][j-k \times cost[i] + k \times valum[i]\}$ $(0\leq k \leq amount[i] 且 0\leq k \times cost[i] \leq V)$

时间复杂度:O($V \times {\sum_{i=1}^N{amount[i]}}$)，空间复杂度:O(NV)。

优化

amount[i]==1时，当01背包处理。

amount[i]$ \times $cost>=V时，当完全背包处理。

amount[i]$ \geq $1时，采用二进制拆分，从而转换成01背包求解，具体如下：
在上面的状态转移方程中，我们让k从1$ \to $amount[i]来实现拿不同的个数，从而转换成01背包问题，但我们可以发现，我们只要将amount[i]拆分成几个数，就可以用他们组合成小于amount[i]的任何数。例如:amount[i]=11,11的二进制为1011，把11拆成100(4)、0010(2)、0001(1)、4(11-4-2-1),这样就可以用4、2、1、4来组合成11以内所有的整数，这样放第这种物品时本来放11次，现在只要放4次，虽然仍然有重复，但也实现了优化。

初始化

如果题目没有要求必须装满，那么我们只要将dp数组全部置为0即可。

如果必须装满，我们就将dp[0]初始化为0，其他初始化为$-\infty$。

完整代码

#include<iostream>
#include<algorithm>  
#include<string.h>  
#include<string>   
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define M 100000000
typedef unsigned long long LL;
typedef  long long ll;
const int mod =1e9+7;

int V,dp[120002];

void ZeroOnePack(int cost,int valum)		//01背包问题
{
    for(int i=V;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+valum);
    return; 
}

void CompletePack(int cost,int valum)		//完全背包问题
{
    for(int i=cost;i<=V;i++)
        dp[i]=max(dp[i],dp[i-cost]+valum);
    return;
}

void MultiplePack(int cost,int valum,int amount)	//多重背包问题
{
    if(cost*amount>=V)
        CompletePack(cost,valum);
    else
    {
        int k=1;
        while(k<amount)
        {
            ZeroOnePack(cost*k,valum*k);
            amount-=k;
            k=k<<1; 	//k*=2
        }
        ZeroOnePack(cost*amount,valum*amount);
     }
    return; 
}

int main()
{
    int n,cost[1000],valum[1000],amount[1000];
    while(cin>>n>>V)
    {
        CRL(dp);
        for(int i=1;i<=n;i++)
            cin>>cost[i]>>valum[i]>>amount[i];
        
        for(int i=1;i<=n;i++)
            MultiplePack(cost[i],valum[i],amount[i]);
        
        cout<<dp[V]<<endl;
    }
    return 0;
}

例题

换一种问法而已：poj 1014

参考资料

《背包九讲》