目录

兑换零钱_牛客题霸_牛客网

最少的完全平方数_牛客题霸_牛客网

装箱问题_牛客题霸_牛客网

求组成aim的最少货币数。

描述

给定数组arrarr中所有的值都为正整数且不重复。每个值代表一种面值的货币每种面值的货币可以使用任意张再给定一个aim代表要找的钱数求组成aim的最少货币数。

如果无解请返回-1.

数据范围数组大小满足 0≤n≤100000≤n≤10000 数组中每个数字都满足 0<val≤100000<val≤100000≤aim≤50000≤aim≤5000

要求时间复杂度 O(n×aim)O(n×aim) 空间复杂度 O(aim)O(aim)。

输入描述

第一行给定两个正整数分别是 n 和 aim 分别表示数组 arr 的长度和要找的钱数。

第二行给定 n 个正整数表示 arr 数组中的所有元素

输出描述

输出组成 aim 的最少货币数

组成aim的最少货币数初始化dp数组为(aim+1, aim+1)  dp[0] = 1;

#include <iostream>
using namespace std;
#include<vector>

int main() {
    int n, aim;
    cin>>n>>aim;
    int *arr = new int[n];
    for(int i = 0; i < n; i++)
        cin>>arr[i];
    if(aim <1)
    {
        cout<<0<<endl;
        return 0;
    }
    vector<int> dp(aim+1, aim+1);
    dp[0] = 0;  // 注意dp数组的初始化  与dp[0]的初始化
    for(int i = 0; i < n; i++)
    {
        for(int j = arr[i]; j <= aim; j++)
        {
            dp[j] = min(dp[j], dp[j-arr[i]]+1);
        }
    }
    if(dp[aim]==aim+1)
        cout<<-1<<endl;
    else
        cout<<dp[aim]<<endl;

    delete[]arr;
    return 0;
}
// 64 位输出请用 printf("%lld")

最少的完全平方数

描述

给定一个正整数n请找出最少个数的完全平方数使得这些完全平方数的和等于n。

完全平方指用一个整数乘以自己例如1*12*23*3等依此类推。若一个数能表示成某个整数的平方的形式则称这个数为完全平方数。例如:149和16都是完全平方数但是235811等等不是

数据范围:1≤n≤104​1≤n≤104​

输入描述

仅一行输入一个正整数 n 

输出描述

按题目要求输出完全平方数之和为n的最少个数

#include <iostream>
using namespace std;
#include<vector>

int main() {
    int n;
    cin>>n;

    vector<int>dp(n+1, n+1);
    dp[0] = 0;
    for(int i = 1; i*i <= n; i++)
    {
        for(int j = i*i; j <= n; j++)
        {
            dp[j] = min(dp[j], dp[j-i*i]+1);
        }
    }
    cout<<dp[n];
    return 0;
}
// 64 位输出请用 printf("%lld")

装箱问题_牛客题霸_牛客网

描述

有一个箱子容量为 V 同时有n个物品每个物品有一个体积正整数。每个物品只能使用一次。

要求n个物品中任取若干个装入箱内使箱子的剩余空间为最小。

数据范围 1≤V≤2×104 1≤V≤2×104   1≤n≤30 1≤n≤30  每个物品的体积满足 1≤numi≤2×104 1≤numi​≤2×104 

输入描述

第一行输入一个正整数 V 表示箱子的容量

第二行输入一个正整数 n 表示物品的个数。

后续 n 行每行输入一个正整数表示物品的体积    

输出描述

输出箱子最小剩余空间

#include <iostream>
#include <linux/limits.h>
using namespace std;
#include<vector>

int main() 
{
    int V, n;
    cin>>V>>n;
    vector<int> things(n);
    for(int i = 0; i < n; i++)
        cin>>things[i];
    vector<int> dp(V+1);
    for(int i = 0; i < n; i++)
    {
        for(int j = V; j >= things[i]; j--)
        {
            dp[j] = max(dp[j], dp[j-things[i]]+things[i]);
        }
    }
    int l = V-dp[V];
    cout<<l<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")