贪心算法-简单装载

经典算法

贪心算法-简单装载

阅读量: 110 编辑

有 n 件物品（每个物品只有1件）和一个容量为 C 的背包。第 i 件物品的重量是 w[i]。物品不可分割，求解将哪些物品装入背包可物品数量最多。

贪心策略：将物品重量从小到大进行排序，优先挑重量轻的装入背包。

【输入描述】

输入两行。第一行是数组大小 n 和背包容量 C；第二行是每件物品的重量，用空格分开；

【输出描述】

输出若一行，输出能装入背包的物品的重量。

【输入样例】

8 20
7 13 4 5 8 1 11 9

【输出样例】

1 4 5 7

【参考程序】

// 爱码岛编程
#include <bits/stdc++.h>
using namespace std;

int arr[10001]; //重量

int main() {
    int n, C;
    cin >> n >> C;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    sort(arr + 1, arr + n + 1);

    int i = 1, total = 0;
    while (i <= n) {
        if (total + arr[i] <= C) {
            total += arr[i];
            cout << arr[i] << " "; //物品重量
        }
        i++;
    }

    return 0;
}