算法读资料总结——背包问题（12）

算法读资料总结——背包问题（12）

目录

总结

01背包问题

Charm Bracelet（题目链接）

完全背包问题

poj Dollar Dayz 3181（题目链接）

HDU - 1114 Piggy-Bank （题目链接）

DP其它问题

总结

上一周因为考试的原因没有写博客，所以这周也加紧了任务。这周是这个课的最后一周，也算是走了一段路了，接下来任重而道远。近两个星期学的背包问题，大约看了80篇博客，对这个问题也有一定的见解。背包问题也属于动态规划之列，分为01背包问题、和完全背包问题。再加上更加深入的动态问题有了更好的理解。

01背包问题

一般背包问题，描述为有n件物品，每件物品的重量一定但是价值不同，有一个容量为V的背包，求使得背包物品总价值最大的方法。

如果用暴力枚举那么复杂度就很高了，时间复杂度为O（n^2）,如果用背包来求解的话那么时间复杂度为O（nV）其中比较重要的是状态转移方程。

dp[i][v]=max{dp{[i-1][v],dp[i-1][v-w[i]]+c[i]} //(1<=i<=n,w[i]<=v<=V)

在此问题中，空间复杂度可以进一步优化，稍微修改下状态转移方程即可。

当时在试01背包时，没有考虑到用一维数组必须是逆序，开始用顺序做一直在报错，考虑了很久才明白怎么回事。如果用顺序做下去的话，到最后减一个负数是没有意义的。而用二维数组则没有这个问题。

Charm Bracelet（题目链接）

题目大意：有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

for (int i = 0; i < N; i++){for (int j = M; j>=Wi[i]; j--){dp[j] = max(dp[j],dp[j-Wi[i]]+Di[i]);

小结：很经典的01背包问题，有固定的套路了

完全背包问题

完全背包问题与01背包的问题的而区别就是，完全背包问题每种物品都有无穷件。其的状态转移方程为：

dp[i][v]=max(dp[i-1][v],dp[i][v-w]]+c[i])

poj Dollar Dayz 3181（题目链接）

题目大意：输入n,k，用任意多个1--k之间的数组成n，问总共有多少种方法

for(int i=1;i<=k;i++){for(int j=i;j<=n;j++){a[j]=a[j]+a[j-i]+(b[j]+b[j-i])/INF;b[j]=(b[j]+b[j-i])%INF;}}

小结：用完全背包可以很好的优化问题，开始没用完全背包，代码长度是优化后的近两倍

HDU - 1114 Piggy-Bank （题目链接）

题目大意：先输入n,m，表示空罐的质量，和现在装了钱的罐子的质量，再输入一个t，表示，有t种规格不同的硬币，接下来输入t行，每行两个数p[i],w[i],分别表示硬币的价值和它的重量，现在问这个罐子里能存放的最少的钱数是多少？

for(i=0;i<t;i++)
{
for(j=w[i];j<=sum;j++)
{
dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
}
}

小结：多重背包问题，多用几次循环即可。

DP其它问题

最大子数和（题目链接）

题目大意：一朵花卉有N朵花，有N-1条枝条与之连接，求通过修剪使得花变成最漂亮的。

for(int i=1;i<n;i++){int u,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);//vector双向连边}dfs(1,0);for(int i=1;i<=n;i++)ans=max(ans,f[i]);//找出最大点权和

小结：随意一点，不妨假设1节点就是根节点。根节点确定祖宗关系也就随之确定了。