侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 628 篇文章
  • 累计创建 127 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【动态规划】买书

GabrielxD
2023-02-17 / 0 评论 / 0 点赞 / 21 阅读 / 316 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-02-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1023. 买书 - AcWing题库


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

问小明有多少种买书方案?(每种书可购买多本)

输入格式

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

输出格式

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

数据范围

0n10000 \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]);
    }
}
0

评论区