阅读背景:

输出字典序最小的背包方案

来源:互联网 
#include<iostream>
using namespace std;
int c[maxn],v[maxn];
int main()
{
    int n,V;
    cin>>n>>V;
    //先逆序,从后向前,这样有利于输出时是按照最小字典序来
    for(int i=n;i>=1;i--)
    {
        cin>>c[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=c[i];j--)
        {
            f[j]=max(f[j],f[j-c[i]]+v[i]);
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(f[V]==f[V-c[i]]+v[i])//两者相同以选序号最小的情况为主
        {
            cout<<n-i+1<<' ';
            V-=c[i];
        }
    }
	return 0;
}#include<iostream>
using namespace std;
int c[m



你的当前访问异常,请进行认证后继续阅读剩余内容。

分享到: