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

i 件物品的体积是 vi,价值是 wi

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

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

输入格式

第一行两个整数,NV,用空格隔开,分别表示物品数量和背包容积。

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

输出格式

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

物品编号范围是 1N

数据范围

0 < N, V ≤ 1000

0 < vi, wi ≤ 1000

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例

1 4

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, V, v[N], w[N], dp[N][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; --i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i + 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
        }
    }
    int j = V;
    for (int i = 1; i <= n; ++i) {
        if (j >= v[i] && dp[i][j] == dp[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    }
    return 0;
} 
分类: AlgorithmDP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status