SYZOJ - sxy的书包(背包)

题目链接:https://syzoj.com/problem/27
内存限制：128 MiB 时间限制：500 ms

题目描述

sxy有很多书，书包可能会装不下全部的书（啊，你想问我为什么说是可能会？）。他想尽可能装多的书，但是书太多了书包装不下，太重了不想背。现在输入N，表示书的总数，输入V表示书包容积，输入M表示sxy能容忍的书包最大重量。后面输入每本书的体积和重量，问sxy最多能背走多少本书

输入格式

第一行，三个整数，分别为N（书的总数），V（书包容积），M（最大重量）

后面输入共有N行，第1行输入第一本书的体积，第一本书的质量，以此类推

输出格式

输出sxy能背走的最多书的数量

样例输入

3 10 16 
3 6
7 8
4 8

样例输出

2

数据范围与提示

0 <= N <= 30;
0 <= V <= 1000;
0 <= M <= 2000;
每个物品的体积不超过100，重量不超过200.

解题思路

背包问题。

#include <bits/stdc++.h>
using namespace std;
int vol[35], wei[35], dp[1005][2005];
int main() {
    int n, v, w;
    scanf("%d%d%d", &n, &v, &w);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &vol[i], &wei[i]);
    for (int i = 0; i < n; i++)
        for (int j = v; j >= vol[i]; j--)
            for (int k = w; k >= wei[i]; k--)
                dp[j][k] = max(dp[j][k], dp[j - vol[i]][k - wei[i]] + 1);
    printf("%d\n", dp[v][w]);
    return 0;
}