题目描述
求01背包中字典序最小的物品选法,且使得背包中物品的价值和最大。
算法1
(01背包)
这里采用从结果向过程推导的方法解答。
时间复杂度
O(n * m)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i ++ )
#define ref(i, j, k) for(int i = j; i >= k; i -- )
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, f[N][N], w[N], v[N];
signed main()
{
cin >> n >> m;
ref(i, n, 1)
cin >> w[i] >> v[i];
f(i, 1, n)
ref(j, m, 0)
{
f[i][j] = f[i-1][j];
if(j >= w[i]) f[i][j] = max(f[i][j], f[i-1][j - w[i]] + v[i]);
}
int k = m;
ref(i, n, 1)
if(k >= w[i] && f[i][k] == f[i-1][k - w[i]] + v[i])
{
cout << n - i + 1 << " ";
k -= w[i];
}
cout << endl;
}