【动态规划】买书

题目

1023. 买书 - AcWing题库

---

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式

一个整数 n，代表总共钱数。

输出格式

一个整数，代表选择方案种数。

数据范围

$0 \le n \le 1000$

输入样例1：

20

输出样例1：

2

输入样例2：

15

输出样例2：

0

输入样例3：

0

输出样例3：

1

解题

方法一：动态规划

思路

本题是：完全背包问题的应用：完全背包问题求方案数。

思路和代码与01背包问题求方案数大同小异，思路参见：01背包问题求方案数 - 数字组合 - 思路。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int c = (int) in.nval;
        int n = 4;
        int[] v = {10, 20, 50, 100};
        int[] f = new int[c + 1];
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = v[i]; j <= c; ++j) {
                f[j] += f[j - v[i]];
            }
        }
        System.out.println(f[c]);
    }
}

#include <iostream>

using namespace std;

const int N = 1010;
int n;
int v[] = {10, 20, 50, 100};
int f[N];

int main() {
    scanf("%d", &n);
    f[0] = 1;
    for (int& vi : v) {
        for (int j = vi; j <= n; ++j) {
            f[j] += f[j - vi];
        }
    }
    printf("%d\n", f[n]);

    return 0;
}