月度归档:2017年11月

动态规划-完全背包问题

Description

有 n 个重量和价值分别为 wi, vi 的物品。从这些物品中挑选出总重量不超过 W 的物品,求所有挑选方案中价值总和的最大值。在这里,每种物品可以挑选任意多件。

Input

第一行为 n 和 W, 1 ≤ n ≤ 100, 1 ≤ W ≤ 10000
之后 n 行每行为 wi, vi, 1 ≤ wi, vi ≤ 100

Output

输出符合题目要求的价值总和的最大值

Sample Input

3 7
3 4
4 5
2 3

Sample Output

10

Hint

01 背包问题与完全背包问题的不同之处在于后者的每件物品可以无限次数选取,因此后者只能递增顺序求解。对于每个物品,我们可以选取 0 件,1 件,…,W/wi 件。对于每个子问题,我们可以转化为“将前 i-1 种物品放入质量为 V 的背包内”,价值为 dp[i - 1][j],“将前 i-1 种物品放入质量为 V - vi*k 的背包内”,价值为 dp[i - 1][j - k * item[i][0]] + k * item[i][1],以及“将前 i-1 种物品放入质量为 V - vi * (k - 1) 的背包内”,价值为 dp[i - 1][j - (k - 1) * item[i][0]] + (k - 1) * item[i][1]

Optimization

空间和时间复杂度优化

因为我们是递增计算,之前所存储的所有结果都是该状态下的最优解,所以我们不需要第三层循环来枚举在当前质量下最合适的当前物品个数。换言之,在考虑“是否放入第 i 件物品”的决策时,需要使用已经放入了第 i 件物品的子状态 dp[i][W - wi]时,只需调用其最优子状态即可。

时间复杂度优化

因为每种物品的个数都是无限的,所以对于 wi > wj 且 vi < vj 的物品 i 可以直接丢弃,整体复杂度约 O(n^2)。

题解

#include <cstdio>
inline int max(int a, int b)
{
    return a > b ? a : b;
}
int dp[10010], n, w;
int main()
{   
    scanf("%d%d", &n, &w);
    int item[n+1][2];
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &item[i][0], &item[i][1]);
        for (int j = 1; j < i; j++)
        {
            if (item[i][0] > item[j][0] && item[i][1] < item[j][1])
            {
                n--;
                i--;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = item[i][0]; j <= w; j++)
        {
            if (j < item[i][0])
                dp[j] = dp[j-1];
            else
                dp[j] = max(dp[j], dp[j - item[i][0]] + item[i][1]);
        }
    } 
    printf("%d\n", dp[w]);
    return 0;
}

动态规划-01 背包问题

Description

有 n 个重量和价值分别为 wi, vi 的物品。从这些物品中挑选出总质量不超过 W 的物品,求所有挑选方案中价值总和的最大值。

Input

第一行为 n 和 W, 1 ≤ n ≤ 100, 1 ≤ W ≤ 10000
之后 n 行每行为 wi, vi, 1 ≤ wi, vi ≤ 100

Output

输出符合题目要求的价值总和最大值

Sample Input

4 5
2 3
1 2
3 4
2 2

Sample Output

7

Hint

每个物品只有一件,对于每个物品我们只能选择放或不放。如果不放置,问题转化为“前 i-1 件物品放入质量为 W 的背包内”,价值为 dp[i-1][W]。如果放置,问题则转化为“前 i-1 件物品放入质量为 W-wi 的背包内”,价值为 dp[i-1][W-wi] + vi

Optimization

优化空间复杂度

若将程序从递增计算的方式修改为以 W 递减的方式,这样在计算 dp[v] 的时候 dp[v-vi] 的值就是之前 dp[i-1][V-vi] 的值。从而节省了一个维度的空间。

题解

#include <cstdio>
int n, w, item[110][2], dp[110][10010], t;//item[i][0] weight i, item[i][1] value i
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int solve()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j < item[i][0])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i][0]] + item[i][1]);
        }
    }
    printf("%d\n", dp[n][w]);
}
int main()
{
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &item[i][0], &item[i][1]);
    solve();
    return 0;
}

C 由实现定义的行为、未定义的行为与未明确的行为

Implementation-defined behavior

由实现定义的行为。例如,int 数据类型的内存空间大小为一般为 4 bytes。

Undefined behavior

未定义的行为。如果程序违反(或者超出) C 标准的规则定义,其执行的结果是无法预料的,换言之,对于这段语句,编译器不用理解(编译器可以不管它,也可以做任何事,包括让你女盆友怀孕 —— bumfod)可以做任何方式的理解,因此得到任何结果都是有可能的。例如,整数溢出就是一个 undefined behavior。

例如,对于如下代码

#include 
using namespace std;
int main()
{
    int n=1;
    cout<< n << " " << (n = n - 3) << " " << (n = n + 2);
    return 0;
}

g++ (i686-posix-dwarf-rev2, Built by MinGW-W64 project) 7.1.0 的编译运行结果为 1 -2 0,而g++ (GCC-6.3.0-1) 6.3.0 的结果为 0 0 0
“modify 和 read 之间没有 sequential point 就是 undefined behavior” —— bumfod.

Unspecified behavior

未明确的行为。对于有歧义的语句,可以按照任何可行的方式来解释。例如,函数在计算其参数时的顺序(求值顺序)就是一个 unspecified behavior,程序以任何顺序计算都可以。除此之外,形如 i = i+++i++; 的值也算是 unspecified behavior。因此我们要注意,在实际情况中不要使用依赖编译器具体实现的代码!

区间调度问题

Description

有 n 项工作,每项工作分别在 si 时间开始,在 ti 时间结束。对于每项工作,你都可以选择参与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(既是是开始的瞬间和结束的瞬间重叠也是不允许的)

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?

Input

第一行输入一个数 n (1 ≤ n ≤ 100000),表示工作的数量
接下来的 n 行,第 1 + i (1 ≤ i ≤ n) 行包含两个数 si, ti (1 ≤ si ≤ ti ≤ 10^9),分别为起始时间和结束时间。

Output

输出为一行,包含一个整数,为能参与的工作数的最大值

Sample Input

5
1 3
2 5
4 7
6 9
8 10

Sample Output

3

Hint

每一次都选取结束时间最早的事件。因为与其他选择方案相比,该算法的选择方案在选取了相同数量的更早开始的工作时,
其最终结束时间不会比其他方案的更晚。所以,不存在选取更多工作的选择方案。
通过定义 compare 函数实现 sort() 的自定义排序规则。

题解

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 100100
using namespace std;
int sum = 0;

struct node
{
    int start, end;
}arr[INF];

bool cmp(const node& i, const node& j)
{
    if (i.end > j.end)
        return 0;
    else
        if (i.end == j.end && i.start > j.start)
            return 0;
    return 1;
}

inline int find(int addr, int n)
{
    for (int i = addr + 1; i < n; i++)
        if (arr[i].start > arr[addr].end){
            return i;
        }
    return n+1;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &arr[i].start, &arr[i].end);
    sort(arr,arr+n,cmp);
    for (int addr = 0; addr < n; addr = find(addr, n))
        sum++;
    printf("%d\n", sum);
    return 0;
}