首页 > 其他 > 详细

Re0:DP学习之路 01背包如何打印路径?

时间:2019-01-06 11:07:00      阅读:144      评论:0      收藏:0      [点我收藏+]

伪代码

用二维数组记录,如果出现可以转移的dp那么记录bk[当前体积][装的物品]=1

输出的时候倒推,如果存在连通的边那么输出并且总共的体积减去输出的体积

代码(uva-624,目前wa不明所以,网上的答案也是那么输出的,或许要输出最多的物品?目前也不会这种玩法)

#include <bits/stdc++.h>
using namespace std;
int v[1000],dp[1000000],bk[1000][1000];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  while(cin>>m>>n)
  {
    memset(dp,0,sizeof(dp));
    memset(bk,0,sizeof(bk));
    stack<int> st;
    for(int i=1;i<=n;i++)
    cin>>v[i];
    for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
    if(dp[j]<dp[j-v[i]]+v[i])
    {
      bk[j][i]=1;
      dp[j]=dp[j-v[i]]+v[i];
    }
    for(int i=n,j=m;i>=1;i--)
    if(bk[j][i])
    st.push(v[i]),j-=v[i];
    while(st.size())
    {
      cout<<st.top()<<" ";
      st.pop();
    }
    cout<<"sum:"<<dp[m]<<"\n";
  }
}

Re0:DP学习之路 01背包如何打印路径?

原文:https://www.cnblogs.com/baccano-acmer/p/10227387.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!