C++

C++ – 基础背包问题

XU

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？

输入输出格式

输入格式

第一行有22个整数T(1 \le T \le 1000)T(1≤T≤1000)和M(1 \le M \le 100)M(1≤M≤100)，用一个空格隔开，TT代表总共能够用来采药的时间，MM代表山洞里的草药的数目。 接下来的MM行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

1个整数，表示在规定的时间内可以采到的草药的最大总价值。

样例

样例输入

70 3
71 100
69 1
1 2

样例输出：

3

（ps；题目来源 洛谷 p1048）

题解

这是一道标准的背包问题，背包属于动态规划中较为常见的题型，其基本理念为在规定的 容量/总价/时间 的限定中尽可能寻求最大的收益。其递推公式大致为

if(j>s[i].s) dp[i][j]=max（dp[i-1][j-s[i].s]+s[i].v,dp[i-1][j]） else dp[i][j]=dp[i-1][j]; (ps:s[i].s代表第i件物品所占空间，s[i].v代表其价值。dp[i][j]代表当背包大小为j时的最大总价。i代表当前正在判断是否装入背包的物品。故dp[n][m] 便是最大值。 ） 代码如下；（ps；本代码加入了输出被选入物品名单的部分。）

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node {
    int v, s;
};
node va[101];
int dp[103][1100];
int main() {
    int c, n;
    scanf("%d %d", &c, &n);
    int tem[n];
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &va[i].s, &va[i].v);
    for(int i = 1; i <= n; i++)
        //初始化dp[i][j]便于之后比较。
        dp[i][0] = 0;
    for(int j = 0; j <= c; j++)
        dp[0][j] = 0;
    for(int i = 1; i <= n; i++) {
        //双重循环遍历每个位置。
        for(int j = 0; j <= c; j++) {
            if(va[i].s > j)
                //判断当前背包是否能装下第i件物品。
                dp[i][j] = dp[i - 1][j];
            else {
                if(dp[i - 1][j - va[i].s] + va[i].v > dp[i - 1][j])
                    //对比装了物品前后的总价值取最大的。
                    dp[i][j] = dp[i - 1][j - va[i].s] + va[i].v;
                else dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n][c] << endl;
    //输出最大值。
    for(int i = 1; i <= n; i++) tem[i] = 0;
    int j = c;
    for(int i = n; i > 0; i--) {
        if(dp[i][j] > dp[i - 1][j]) {
            tem[i] = 1;
            j = j - va[i].s;
        }
    }
    for(int i = 1; i <= n; i++)
        if(tem[i] == 1) cout << i << ' ';
    return 0;
}
/*附样例输入
15 5
2 6
2 3
6 5
5 4
4 6*/
/*表格输出方便研究。
  0__1__2__3__4__5__6__7__8__9_10_11_12_13_14_15
0!0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0!
1!0  0  6  6  6  6  6  6  6  6  6  6  6  6  6  6!
2!0  0  6  6  9  9  9  9  9  9  9  9  9  9  9  9!
3!0  0  6  6  9  9  9  9 11 11 14 14 14 14 14 14!
4!0  0  6  6  9  9  9 10 11 13 14 14 14 15 15 18! 
5!0  6  6  9  9 12 12 15 15 15 16 17 19 20 20 20! */

发表回复