完全背包问题

这个经典问题的大致意思是:

有n种物品重量和价值分别为w[i]、v[i]的物品，从这些物品中挑选出总重量不超过W的物品，求出挑选物品价值总和的最大值。每种物品可以挑选任意多件。

利用二维数组dp，其中dp[i+1][j]表示从前i+1种物品(编号从0到i)中挑选出总重量不超过j的物品的价值总和的最大值。显然有

dp[0][j]=0;

dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i])(k>=0);

按照上述递推式可以写出如下代码:

int n,W;
int w[105];
int v[105];
int dp[105][10005];
//从第i个物品开始挑选总重不超过j的物品，注意物品的编号是从0到n-1
void solve()
{
                for(int i=0;i<n;i++){
                                for(int j=0;j<=W;j++){
                                                for(int k=0;k*w[i]<=j;k++){
                                                                dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
                                                }
                                }
                }
                cout<<dp[n][W]<<endl;
}

这个算法构成了三重循环，最坏情况下k可能从0到W，因此时间复杂度最坏情况下为O(nW^2)。这个算法的时间效率并不好，因为有好多重复计算的。可以进行一定优化:

dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i])(k>=0)
          =max(dp[i][j],max(dp[i][j-k*w[i]]+k*v[i]))(k>=1)
	  =max(dp[i][j],max(dp[i][j-k*w[i]-w[i]]+k*v[i])+v[i])(k>=0)
	  =max(dp[i][j],dp[i+1][j-w[i]]+v[i])

上述代码可以改进为:

int n,W;
int w[105];
int v[105];
int dp[105][10005];
//从第i个物品开始挑选总重不超过j的物品，注意物品的编号是从0到n-1
void solve()
{
                for(int i=0;i<n;i++){
                                for(int j=0;j<=W;j++){
                                                if(j<w[i]) dp[i+1][j]=dp[i][j];
                                                else dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
                                }
                }
                cout<<dp[n][W]<<endl;
}

和01背包问题一样，也可以采用一个数组实现

void solve()
{
	for(int i=0;i<n;i++){

		for(int j=w[i];j<=W;j++)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	}
	cout<<dp[n][W]<<endl;
}