首页 > 分享 > ACM学习第七周

ACM学习第七周

萌宠菠菠乐园
2024-11-04 18:14

01背包

如果我们设vi为第i个物品的价值，wi为第i个物品的体积，则可定义v(i,j)表示容量为j的背包与前i个物品最佳组合的对应价值。
因此我们可以得到递推式：
1>如果包的容量比该物品的体积小，也就是说无法装下，在这个时候其价值与前i-1个的价值是一样的，即v(i,j)=v(i-1,j);
2>如果有足够容量装下物品，那我们要看它能否达到当前的最优价值，于是v(i,j）=max{v(i-1),j),v(i-1,j-w(i))+v(i)};
注：v(i-1,j）表示不装，v(i-1,j-w(i))+v(i)表示装了第i个物品，背包容量减少了w(i)，但价值增加了v(i)。

例题：
一个手镯，贝西想从N个可用的魅力中尽可能地填充它，在提供的列表中，每个魅力值i都有一个权重wi，一个“合意”因子di，并且最多可以使用一次，贝西只能支持重量不超过M的魅力手镯。要推导出评级最大可能。
分析：

#include<iostream> int W[3500]; int D[3500]; int f[13000]; int main() { int ans,max,n,i,j; cin>>n; cin>>max; for(i=0;i<n;i++) { cin>>W[i]; cin>>D[i]; } for(i=0;i<n;i++) { for(j=max;j>0;j--) { if(j>=W[i]&&f[j]<f[j-W[i]]+D[i])//如果还有容量可以装，并且装后为目前最优价值，则装 f[j]=f[j-W[i]]+D[i]; } } ans=0; for(i=0;i<=max;i++) { if(f[i]>ans) ans=f[i];//找出最优价值 } cout<<ans<<endl; return 0;

123456789101112131415161718192021222324252627282930

也可写为

f[j]=max(f[j],f[j-w[i]]+D[j]); 1

这样就不需要再用for遍历找最优解，代码更简单。

完全背包

与01背包不同，在01背包中我们是最多只能拿一件物品，而完全背包则是只要空间够多，一种物品可以拿n件。
状态转移方程：v(i,j)=max(v(i-1,j),v(i,j-w(i))+v(i));

例题：
有个存钱罐，自身重量w1，存满之后重量为w2，所以钱的重量就是w=w2-w1…现在给出n种存钱罐中的钱币价值和重量，求存钱罐存满的情况下(即钱的总重量为w)，所有钱的总价值最小是多少。
分析：
由于每一件物品的数量是无限的，所以是一道完全背包问题。然后分析条件，该题限制的条件是硬币总重量正好等于m，我们要求总价值尽量最小，则初始化dp[0]=0,而其他应该全部初始化为inf

#include<cstring> #include<algorithm> #include<iostream> using namespace std; #define inf 2139062143 int dp[20000]; int main() { int t,w1,w2,n; cin>>t; while(t--) { cin>>w1>>w2>>n; int w=w2-w1; int P,W; memset(dp,127,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++) { cin>>P>>W; for(int j=W;j<=w;j++) dp[j]=min(dp[j],dp[j-W]+P); } if(dp[w]==inf) cout<<"This is impossible.n"; else cout<<"The minimum amount of money in the piggy-bank is "<<dp[w]<<endl; } return 0; }

12345678910111213141516171819202122232425262728293031