题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围
0<N,V≤1000
0<vi,wi≤1000

算法1

与yxc代码大神的代码不同，我是用了判断字典序的方法，确实麻烦了不少

C++ 代码

//by hxc 8/18/2020
//url =https://www.acwing.com/problem/content/12/
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
//背包问题求具体方案数
//用一个二维数组来记录每个体积下的具体方案，在迭代的过程中进行计算
const int MAXN=1005;
int v[MAXN]={0};
int w[MAXN]={0};
int f[MAXN]={0};
vector<int> chooseSmallerOne(vector<int> a,vector<int> b)//返回按照字典序a>b
{
    int sizea=a.size();
    int sizeb=b.size();
    if(sizea==0)return b;
    if(sizeb==0)return a;
    int m=min(sizea,sizeb);
    for(int i=0;i<m;i++)
    {
        if(a[i]>b[i])return b;
        else if(a[i]<b[i])return a;
    }
    return a;//两个数组相同，返回同一个   
}
int main()
{
    int n,m;
    cin>>n>>m;   
    vector<int> t={};
    vector<vector<int>> method; 
    //初始化
    for(int i=0;i<=m;i++)
    {
        method.push_back(t);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }//输入每个物品的体积和价值j
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            int temp=max(f[j],f[j-v[i]]+w[i]);
            if(f[j-v[i]]+w[i]>=f[j]) 
            {
                vector<int> t=method[j-v[i]];
                t.push_back(i);
                if(f[j-v[i]]+w[i]>f[j])
                method[j]=t;
                else
                method[j]=chooseSmallerOne(t,method[j]);//bug如果它们的价值一样真的可以随便选一个么？不可以因为它们的体积
                //是不同的呀！
            }
            f[j]=temp;
        }
    }
    for(int i=0;i<method[m].size();i++)
    {
        cout<<method[m][i]<<' ';
    }
    system("pause");
    return 0;
}