蓝桥杯算法提高VIP-01背包 （C++代码）

解题思路:

    简单的dp问题。

    定义状态：dp[i][j]表示前i件物品(部分或全部)恰放入一个容量为j的背包时可以获得的最大价值。

    则状态转移方程：dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}。

    解释“将前i件物品放入容量为j的背包中”这个子问题：若只考虑第i件物品放/不放，那么该子问题就可以转化为一个只牵扯前i-1件物品的问题。

    ① 不放第i件物品：问题就转化为“前i-1件物品放入容量为c的背包中”

    ② 放第i件物品：问题就转化为“前i-1件物品放入剩下的容量为c-w[i]的背包中”，此时能获得的最大价值就是dp[i-1][c-w[i]]再加上通过放入第i件物品获得的价值v[i],即：dp[i-1][c-w[i]]+v[i]。

注意事项:

    1.考虑到本题题目描述中没有物品和容量的限制，所以用动态数组实现，看起来比较麻烦，但是能保证数组空间不会出现问题，也不会浪费。    

    2.以上方法的时间和空间复杂度均为O(n*c)，时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(c)。(其中n表示物品的数量，c表示背包的容量）

参考代码:

//方法1：用二维数组实现，填表
#include <bits/stdc++.h> 
using namespace std;
int opt_01(int *v,int *w,int n,int c)
{
	int **dp=new int*[n+1];
	for(int i=0;i<n+1;i++)
		dp[i]=new int[c+1];
	for(int j=0;j<c+1;j++)
		dp[0][j]=0;
	for(int i=1;i<n+1;i++)
		dp[i][0]=0;
	for(int i=1;i<=n;i++)
	{		
		for(int j=1;j<=c;j++)
		{
			if(j>=w[i])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	int max=dp[n][c];
	for(int i=0;i<n+1;i++) delete []dp[i];
	delete []dp; 
	return max;
}
int main()
{
	int n,c;
	cin>>n>>c;
	int *v=new int[n+1];
	int *w=new int[n+1];
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	cout<<opt_01(v,w,n,c);	
	delete []v; 
	delete []w;
	return 0;
}

//方法2：空间优化代码，用一维数组实现
#include <bits/stdc++.h> 
using namespace std;
int opt_01(int *v,int *w,int n,int c)
{
	int *dp=new int[c+1];
	memset(dp,0,sizeof(int)*(c+1)); 
	for(int i=1;i<=n;i++)
		for(int j=c;j>=w[i];j--)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	int max=dp[c];
	delete []dp; 
	return max;
}
int main()
{
	int n,c;
	cin>>n>>c;
	int *v=new int[n+1];
	int *w=new int[n+1];
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	cout<<opt_01(v,w,n,c);	
	delete []v; 
	delete []w;
	return 0;
}