个人技术分享

算法提高之背包问题背包问题求具体方案

• 核心思想：01背包 + dp输出方案

  • 因为求字典序最小的方案 所以当取第i个物品时 下一步要求的就是i+1 ~ n的最大方案

  • 所以f意义改变 变成了第i个元素到最后一个元素总容量为j的最优解

    • 之前是前i个物品总容量为j的最优解

  • 这样在之后递归从1~n找方案时 遇到分叉路径会优先取 而不是不取

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 1010;
    
    int f[N][N];
    int v[N],w[N],path[N];
    int n,m,cnt;
    
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=n;i;i--)
        {
            for(int j=0;j<=m;j++)
            {
                f[i][j] = f[i+1][j];  //都是i-1改成i+1
                if(j>=v[i]) f[i][j] = max(f[i][j],f[i+1][j-v[i]] + w[i]);
            }
        }
        for(int i=1,j=m;i<=n;i++)
        {
            if(j>=v[i] && f[i][j] == f[i+1][j-v[i]] + w[i])  //都是i-1改成i+1
            {
                path[cnt++] = i;
                j -= v[i];
            }
        }
        for(int i=0;i<cnt;i++)
        {
            cout<<path[i]<<" ";
        }
    }