伪代码

用二维数组记录，如果出现可以转移的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背包如何打印路径？

伪代码

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

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

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

最新文章

热门文章