题目大意:
购物,买相应物品之前必须先买能装相应物品的盒子,现在已知n个盒子的价钱,以及每个盒子能装的物品数,以及这些物品的价值和花费。为w钱下能买到物品的最大价值。
思路:背包。首先很容易想到的一个状态转移方程是:
DP[i][j]=MAX{DP[i-1][j],MAX{DP[i-1][j-k]+Pack[i][k]}}。其中
DP[i][j]表示前i个盒子中,在金钱j下所能得到的最大价值。考虑第i个盒子选和不选,以及选的话分配多少钱给i。
然而很明显上述时间复杂度过高。考虑优化。仔细分析,会发现MAX{DP[i-1][j-k]+Pack[i][k]},
实际上表示的是在金钱j下且一定考虑第i个盒子下的最大价值。将盒子的价值看作0,在金钱j下首先将盒子的价钱考虑进去。那么剩下的只是挑选i盒子中的物品,即01背包。令f(i,j)为前i个盒子中且第i个盒子必须考虑时在金钱j下的
所得最大价值。那么该初始值f(i,j)=DP[i-1][j-Pbox[i]]+0;初始值确定以后(相当于已经忽略了盒子的影响)。那么直接背包即可。
——————转载
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define M 100001 int dp[51][M],n; int main() { int n,v; while(scanf("%d%d",&n,&v)!=EOF){ memset(dp,-1,sizeof dp); memset(dp[0],sizeof dp[0]); for(int i=1;i<=n;++i){ int x,p; scanf("%d%d",&x,&p); for(int j=x;j<=v;++j) dp[i][j]=dp[i-1][j-x]; while(p--){ int c,w; scanf("%d%d",&c,&w); for(int j=v;j>=c;--j){ if(dp[i][j-c]!=-1){ dp[i][j]=max(dp[i][j],dp[i][j-c]+w); } } } for(int j=0;j<=v;++j){ dp[i][j]=max(dp[i][j],dp[i-1][j]); } } cout<<dp[n][v]<<endl; } return 0; }原文链接:https://www.f2er.com/javaschema/285429.html