01背包问题，dp和贪心解法（c++11）-白红宇

01背包问题，dp和贪心解法（c++11）

阅读量：4510 次

发布时间：2019-06-08

本文共 1916 字，大约阅读时间需要 6 分钟。

dp解法：

令dp[i]表示容量为i的背包所能得到的最大价值，考虑在当前物品集合中加入1个新考虑的物品i，则有如下状态转移方程：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

#include 
     
      using namespace std;const int M = 1e4;typedef pair

> piv;struct Node { int weight, value; int id; void read() { cin >> weight >> value; } void solve(piv dp[], int M) { for (int i = M; i >= weight; i --) { if (dp[i - weight].first + value > dp[i].first) { dp[i].first = dp[i - weight].first + value; dp[i].second = dp[i - weight].second; dp[i].second.push_back(id); } } }};int n, m;piv dp[M];int main() { puts("请输入背包容量和物品个数："); cin >> m >> n; puts("请输入每个背包的重量（体积）和价值"); Node things; for (int i = 0; i < n; i ++) { things.read(); things.id = i + 1; things.solve(dp, m); } cout << "最大价值为：" << dp[m].first << endl; puts("选择的物品编号："); for (int i = 0; i < dp[m].second.size(); i ++) { cout << dp[m].second[i] << " "; } cout << endl; return 0;}

贪心解法：

按部分背包的贪心策略，优先考虑单位价值高的物品，于是只需要按单位价值从高到低排序，然后依次考虑，能放则放即可。

#include 
     
      using namespace std;const int N = 1e2;struct Node {    int weight, value;    int id;    void read() {        cin >> weight >> value;    }    // 单位价值高的放前面    bool operator< (const Node &that) const {        return value * that.weight > that.value * weight;    }};Node things[N];int n, m;int main() {    puts("请输入背包容量和物品个数：");    cin >> m >> n;    puts("请输入每个背包的重量（体积）和价值");    for (int i = 0; i < n; i ++) {        things[i].read();        things[i].id = i + 1;    }    sort(things, things + n);    int ans = 0;    vector
      
        V;    for (int i = 0; i < n; i ++) {        if (m >= things[i].weight) {            ans += things[i].value;            m -= things[i].weight;            V.push_back(things[i].id);        }    }    cout << "最大价值为：" << ans << endl;    puts("选择的物品编号为：");    for (int i = 0; i < V.size(); i ++) {        cout << V[i] << " ";    }    cout << endl;    return 0;}

转载于:https://www.cnblogs.com/jklongint/p/4921492.html

你可能感兴趣的文章