侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】买书

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

题目

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

评论区