【刷题篇】动态规划-完全背包问题（十一）

文章目录

1、完全背包
2、零钱兑换
3、零钱兑换 II
4、完全平方数

1、完全背包

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

int main()
{
    int n,v;
    cin>>n>>v;
    vector<int> V(n+1);
    vector<int> W(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>V[i]>>W[i];
    }
    vector<int> dp(v+1);
    vector<int> dp1(v+1);

    //（1）求这个背包至多能装多大价值的物品？
    for(int i=1;i<n+1;i++)
    {
        for(int j=V[i];j<v+1;j++)
        {
            dp[j]=max(dp[j],dp[j-V[i]]+W[i]);
        }
    }
    cout<<dp[v]<<endl;
    //（2）若背包恰好装满，求至多能装多大价值的物品？
    //体积凑不了正好的时候就是等于-1
    for(int i=1;i<v+1;i++)
        dp1[i]=-0X3f3f3f3f;
    for(int i=1;i<n+1;i++)
    {
        for(int j=V[i];j<v+1;j++)
        {
            dp1[j]=max(dp1[j],dp1[j-V[i]]+W[i]);
        }
    }
    cout<<(dp1[v]<0?0:dp1[v])<<endl;
    return 0;
}

2、零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        vector<int> dp(amount+1);
        int INF=0x3f3f3f3f;
        for(int j=1;j<amount+1;j++)
            dp[j]=INF;
         
        for(int i=1;i<n+1;i++)
        {
            for(int j=coins[i-1];j<amount+1;j++)
                dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
        }
        return dp[amount]>=INF?-1:dp[amount];
    }
};

3、零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        vector<int> dp(amount+1);
        dp[0]=1;
         
        for(int i=1;i<n+1;i++)
        {
            for(int j=coins[i-1];j<amount+1;j++)
                dp[j]+=dp[j-coins[i-1]];
        }
        return dp[amount];
    }
};

4、完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
public:
    int numSquares(int n) {
        int s=sqrt(n);
        int INF=0x3f3f3f3f;
        vector<int> dp(n+1);
        for(int j=1;j<n+1;j++)
            dp[j]=INF;
        for(int i=1;i<s+1;i++)
        {
            for(int j=i*i;j<n+1;j++)
                dp[j]=min(dp[j],dp[j-i*i]+1);
        }
        return dp[n];
    }
};