heihei12305

dp显著特征:该问题具有最优子结构性质

dp的两个基本要素 最优子结构和 重叠子问题

dp设计主要步骤:

1. 问题具有最优子结构性质
2. 构造最优值的递归关系表达式
3. 最优值的算法描述
4. 构造最优解

01背包

给定n种物品和一个背包，物品i的重量是wi，其价值为vi,背包容量为c，问应该如何选择装入背包中的物品，使得装入背包的物品的总价值最大？


01背包是一个特殊的整数划分问题，具有最优子结构性质

m(i,j) = max{m(i+1,j),m(i+1,j-w[i])+v[i]} j>=w[i]

m(i,j) = m(i+1,j) j<w[i]

m(n,j) = Vn j>=w[n]

m(n,j) = 0 j<w[n]

template<class Type>
void Knapsack(Type v, int w, int c,int n,Type ** m)
{
	int jMax = min(w[n]-1,c);.//先将n填上
	for(int j = 0;j<= jMax;j++)//此时容量比所需要小，装不下，为0
	{
		m[n][j] = 0;
	}
	for(int j = w[n];j<=c;j++)//此时容量比所需要大，可以装下，为v[n]
	{
		m[n][j] = v[n];
	}
	//初始化完成，开始填表
	for(int i = n-1;i>1;i--)
	{
		jMax = min(w[i]-1,c);
		for(int j = 0;j<=jMax;j++)
		{
			m[i][j] = m[i+1][j];
		}
		for(int j = w[i];j<=c;j++)
		{
			m[i][j] = max(m[i+1][j],m[i+1][j-w[i]+v[i]);
		}
	}
	m[1][c] = m[2][c];
	if(c>=w[1])
	{
		m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
	}
}

template<class Type>
void Traceback(Type **m,int w,int c,int n,int x)
{
	for(int i = 1;i<n;i++)
	{
		if(m[i][c]==m[i+1][c])//将是否选取背包记录下来
		{
			x[i] = 0;
		}
		else{
			x[i] = 1;
			c-=w[i];
		}
	}
	x[n] = (m[n][c])?1:0;//或为0，或为v[n]
}

非01背包问题 物品可任意分割=>按照v/w排序，相对价值大的先装

class Package
{
public:
    int carry;
    vector<item> items;
    int n;
    Package(int carry,vector<item> &items) 
    {
        this->carry=carry;
        this->items=items;
        this->n=items.size();
        GetAns();
    }
    void GetAns()
    {
        sort(items.begin(),items.end(),[](const item &a,const item &b)
				 {
						 return ((float)a.v/a.w)>((float)b.v/b.w);
				 });
        int sum=0;
        for(int i=0;i<items.size();i++)
        {
            if(items[i].w+sum>carry)
            {
                items[i].quantity=(float)(carry-sum)/items[i].w;
                break;
            }else
            {
                items[i].quantity=1;
                sum+=items[i].w;
            }
        }
        sort(items.begin(),items.end(),[](item &a,item &b)
        {
                 return a.num<b.num;
        });
    }
    void print()
    {
        float sum = 0;
         cout<<"\t\t";
        for(int i=0;i<n;i++)
        {
            cout<<items[i].num<<"\t";
        }
        cout<<endl;
         cout<<"重量\t";
        for(int i=0;i<n;i++)
        {
            cout<<items[i].w<<"\t";
        }
        cout<<endl;
        cout<<"价值\t";
        for(int i=0;i<n;i++)
        {
            cout<<items[i].v<<"\t";
        }
        cout<<endl;
        cout<<"数量\t";
        for(int i=0;i<n;i++)
        {
            if(items[i].quantity<0.000001)
            {
                items[i].quantity = (int)0;
            }
            cout<<setprecision(3)<<(items[i].quantity)<<"\t";
            sum+=items[i].quantity*items[i].v;
        }
        cout<<setprecision(6)<<endl<<"总价值："<<sum<<endl;
    }
};