首页 > 代码库 > DP入门
DP入门
这段时间要开始刷dp了，记录点点滴滴。21:33:51
一.基础dp：
1.hdu.2602.Bone Collector.
这道是基础的01背包。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=1000+10; 5 int w[MAXN]; 6 int v[MAXN]; 7 int dp[MAXN]; 8 int main() 9 {10 int test;11 scanf("%d",&test);12 while(test--)13 {14 int n,V;15 scanf("%d%d",&n,&V);16 for(int i=1;i<=n;i++)17 scanf("%d",&w[i]);18 for(int i=1;i<=n;i++)19 scanf("%d",&v[i]);20 for(int j=0;j<=V;j++)21 dp[j]=0;22 for(int i=1;i<=n;i++)23 for(int j=V;j>=v[i];j--)24 {25 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);26 }27 int ans=0;28 for(int j=0;j<=V;j++)29 if(dp[j]>ans)30 ans=dp[j];31 printf("%d\n",ans);32 }33 return 0;34 }
2.poj.3624.Charm Bracelet.
基础01背包，注意下标的最大值为物品数还是背包容量最大值。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=3410; 5 const int MAXM=13000; 6 int w[MAXN]; 7 int cost[MAXN]; 8 int dp[MAXM]; 9 int main()10 {11 int n,m;12 while(scanf("%d%d",&n,&m)!=EOF)13 {14 for(int i=1;i<=n;i++)15 scanf("%d%d",&cost[i],&w[i]);16 for(int j=0;j<=m;j++)17 dp[j]=0;18 for(int i=1;i<=n;i++)19 for(int j=m;j>=cost[i];j--)20 dp[j]=max(dp[j],dp[j-cost[i]]+w[i]);21 int ans=0;22 for(int i=0;i<=m;i++)23 if(dp[i]>ans)24 ans=dp[i];25 printf("%d\n",ans);26 }27 return 0;28 }
3.hdu.2546.饭卡.
先预留5元去买最贵的菜，注意n==0 时结束。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=1000+5; 5 const int maxm=1000+5; 6 int a[maxn]; 7 int dp[maxm]; 8 int main() 9 {10 int n;11 while(scanf("%d",&n)!=EOF)12 {13 if(n==0)14 break;15 for(int i=1;i<=n;i++)16 scanf("%d",&a[i]);17 int m;18 scanf("%d",&m);19 if(m<5)20 printf("%d\n",m);21 else22 {23 int mm=m-5;24 sort(a+1,a+n+1);25 for(int i=0;i<=mm;i++)26 dp[i]=0;27 for(int i=1;i<n;i++)28 for(int j=mm;j>=a[i];j--)29 dp[j]=max(dp[j],dp[j-a[i]]+a[i]);30 int ans=0;31 for(int i=0;i<=mm;i++)32 if(dp[i]>ans)33 ans=dp[i];34 printf("%d\n",m-ans-a[n]);35 }36 }37 return 0;38 }
4.uva.562.Dividing Coins
平衡问题，先累加硬币的总价值，然后sum/2，作为背包容量对n个硬币进行选择，求出其最大价值。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=105; 5 const int MAXM=30000; 6 int dp[MAXM]; 7 int coin[MAXN]; 8 int main() 9 {10 int test;11 scanf("%d",&test);12 while(test--)13 {14 int n;15 scanf("%d",&n);16 int sum=0;17 for(int i=1;i<=n;i++)18 {19 scanf("%d",&coin[i]);20 sum+=coin[i];21 }22 int half=sum/2;23 for(int i=0;i<=half;i++)24 dp[i]=0;25 for(int i=1;i<=n;i++)26 for(int j=half;j>=coin[i];j--)27 dp[j]=max(dp[j],dp[j-coin[i]]+coin[i]);28 int cnt=0;29 for(int i=0;i<=half;i++)30 if(dp[i]>cnt)31 cnt=dp[i];32 half=sum-cnt;33 int ans;34 if(half>cnt)35 ans=half-cnt;36 else37 ans=cnt-half;38 printf("%d\n",ans);39 }40 return 0;41 }
5.hdu.2955.Robberies.
被抓的概率比较难算，加之精度问题，所以转换为不被抓的概率。
若以概率为代价，不是整数，无法作为下标，所以以银行总价值为背包容量，单个银行的储蓄为体积，以不被抓的概率作为价值。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN=105; 5 const int MAXM=11000; 6 double dp[MAXM]; 7 int money[MAXN]; 8 double pro[MAXN]; 9 int main()10 {11 int test;12 scanf("%d",&test);13 while(test--)14 {15 int n;16 double P;17 scanf("%lf%d",&P,&n);18 P=1.0-P;19 int sum=0;20 for(int i=1;i<=n;i++)21 {22 scanf("%d%lf",&money[i],&pro[i]);23 sum+=money[i];24 pro[i]=1.0-pro[i];25 }26 for(int i=0;i<=sum;i++)27 dp[i]=0;28 dp[0]=1;29 for(int i=1;i<=n;i++)30 for(int j=sum;j>=money[i];j--)31 dp[j]=max(dp[j],dp[j-money[i]]*pro[i]);32 int ans=0;33 for(int i=0;i<=sum;i++)34 if(dp[i]>=P&&i>ans)35 ans=i;36 printf("%d\n",ans);37 }38 return 0;39 }
DP入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。