背包问题 动态规划解法

#include <iostream>
#include <vector>

using namespace std;

//物品数据结构

class Thing
{
    public:
    int w;
    int v;
    bool selected;
};

int Knapsack(vector<Thing>& things,const int n,const int c)
{
    vector< vector<int> > m(n,vector<int>(c+1,0));
    
    for(int j=0;j<=c;j++)
    {
        if(j>=things[n-1].w)
        {
            m[n-1][j]=things[n-1].v;
        }
        else
        {
            m[n-1][j]=0;
        }
    }
    for(int i=n-2;i>=0;i--)
    {
        for(int j=0;j<=c;j++)
        {
            if(j<things[i].w)
            {
                m[i][j]=m[i+1][j];
            }
            else
            {
                m[i][j]=max(m[i+1][j],m[i+1][j-things[i].w]+things[i].v);
            }
        }
    }
    int total=c;
    for(int i=0;i<n-1;i++)
    {
        if(m[i][total]==m[i+1][total])
        {
            things[i].selected=false;
        }
        else
        {
            things[i].selected=true;
            total-=things[i].w;
        }
    }
    things[n-1].selected=(m[n-1][total]>0)?true:false;
    return m[0][c];
}

int main()
{
    const int c=100;
    const int n=4;
    vector<Thing> things;
    Thing th;
    
    th.w=20;
    th.v=60;
    things.push_back(th);
    
    th.w=50;
    th.v=30;
    things.push_back(th);
    
    th.w=60;
    th.v=29;
    things.push_back(th);
    
    th.w=1;
    th.v=5;
    things.push_back(th);
    
    int rv=Knapsack(things,n,c);
    cout << "max value="<<rv<<endl;

    cout<<endl<<"物品序号:\t\t";
    for(int i=0;i<n;i++)
    {
        cout<<i<<'\t';
    }    
    cout<<endl<<"物品重量:\t\t";
    for(int i=0;i<n;i++)
    {
        cout<<things[i].w<<'\t';
    }
    cout<<endl<<"物品价值:\t\t";
    for(int i=0;i<n;i++)
    {
        cout<<things[i].v<<'\t';
    }
    cout<<endl<<"选择情况:\t\t";
    for(int i=0;i<n;i++)
    {
        cout<<(things[i].selected?"√":"X")<<'\t';
    }
    return 0;
}

运行情况：

max value=95

物品序号: 0 1 2 3

物品重量: 20 50 60 1

物品价值: 60 30 29 5

选择情况: √ √ X √