A-挂饰|01背包

本文主要是介绍A-挂饰|01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4247

刚刚接触到这道题的时候有点乱，大概总的来说有两个思路：

1.暴力搜索(因为有10000ms)

2.直接动态规划--(又要消耗一波脑细胞π_π)；

细读一下题目，便知道每个饰品就只有要或者不要(1||0)两种关系。于是决定用01背包来解决这道题。接下来，怎么办？在做题过程中，我发现有的饰品有挂钩有的没有，那么转移方程写不下去了，但是我发现我可以预处理挂钩的顺序，于是我将挂钩数从大到小排序。

很轻易的写出了转移方程：

for(int i=1;i<=n;i++){for(int j=0;j<=n;j++)dp[i][j]=max(dp[i-1][j],dp[i-1][max(j-s[i].a,0)+1]+s[i].b);}

同时要注意DP数组的预处理，初始化的时候我选择-INF(INF=2000*1e6);

以下是AC代码：

/*
name:Rollchuchy
type:01 package
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[2005][2005];/*dp[i][j]前i个物品j个钩子数的最大幸福值*/
const int INF=2e9;
struct node
{int a,b;} s[2050];bool cmp(node x1,node x2){return x1.a>x2.a;}/*预处理*/
int main()
{//freopen("in.txt","r",stdin);int n;cin>>n;for(int i=1;i<=n;i++)cin>>s[i].a>>s[i].b;sort(s+1,s+n+1,cmp);for(int i=0;i<=n;i++){for(int j=0;j<=n+1;j++)dp[i][j]=-INF; }dp[0][1]=0;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++)dp[i][j]=max(dp[i-1][j],dp[i-1][max(j-s[i].a,0)+1]+s[i].b);}int ans=-INF;for(int i=0;i<=n;i++)ans=max(ans,dp[n][i]);cout<<ans<<endl; return 0;
}

当然啦~这里要宣传一波我朋友的代码：
http://jingwei.site/a-%E6%8C%82%E9%A5%B0-%E8%A1%A5%E5%85%85%E6%8A%A5%E5%91%8A/

他是采用的DFS+剪枝；

以上就是这道题的详解了~

这篇关于A-挂饰|01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---