C++--完全背包问题

这篇具有很好参考价值的文章主要介绍了C++--完全背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.【模板】完全背包_牛客题霸_牛客网

你有一个背包,最多能容纳的体积是V。

现在有n种物品,每种物品有任意多个,第i种物品的体积为vivi​ ,价值为wiwi​。

(1)求这个背包至多能装多大价值的物品?

(2)若背包恰好装满,求至多能装多大价值的物品?

输入描述:

第一行两个整数n和V,表示物品个数和背包体积。

接下来n行,每行两个数vivi​和wiwi​,表示第i种物品的体积和价值。

1≤n,V≤10001≤n,V≤1000

输出描述:

输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。

示例1

输入:

2 6
5 10
3 1
输出:
10
2

示例2

输入:

3 8
3 10
9 1
10 1
输出:
20
0

说明:

无法恰好装满背包。

示例3

输入:

6 13
13 189
17 360
19 870
14 184
6 298
16 242
输出:
596
189

说明:

可以装5号物品2个,达到最大价值298*2=596,若要求恰好装满,只能装1个1号物品,价值为189.
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    int n, V;
    cin >> n >> V;
    int v[n];
    int w[n];
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
    int dp[n + 1][V + 1];
    //初始化
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= V; j++)
        {
            //动态转移方程
            dp[i][j] = dp[i - 1][j];
            if (j - v[i - 1] >= 0) dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
        }
    }
    cout << dp[n][V] << endl;

    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++) dp[0][i] = -1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j - v[i - 1] >= 0 && dp[i][j - v[i - 1]] != -1) dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

2.零钱兑换  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3 
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        int n=coins.size();
        vector<int> dp(amount+1);//创建dp表
        for(int i=1;i<=amount;i++) dp[i]=0x3f3f3f3f;//初始化,寻找最小值
        for(int i=1;i<=n;i++)
        {
            for(int j=coins[i-1];j<=amount;j++)
            {
                
                if(j-coins[i-1]>=0)
                {
                    dp[j]=min(dp[j],dp[j-coins[i-1]]+1);//动态转移方程
                }
            }
        }
        return dp[amount]>=0x3f3f3f3f?-1:dp[amount];//返回值
    }
};

3.零钱兑换二  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:amount = 10, coins = [10] 
输出:1
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;i++)
        {
            for(int j=coins[i-1];j<=amount;j++)
            {
                
                dp[j]+=dp[j-coins[i-1]];//动态转移方程
            }
        }
        return dp[amount];//返回值
    }
};

4.完全平方数  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:文章来源地址https://www.toymoban.com/news/detail-687072.html

输入:n = 13
输出:2
解释:13 = 4 + 9
class Solution {
public:
    int numSquares(int n) 
    {
        int m=sqrt(n);
        vector<int> dp(n+1,0x3f3f3f3f);//初始化
       
        dp[0]=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=i*i;j<=n;j++)
            {
                dp[j]=min(dp[j],dp[j-i*i]+1);//动态转移方程
            }
        }
        return dp[n];       
    }
};

到了这里,关于C++--完全背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 背包问题分析代码详解【01背包+完全背包+多重背包】

    一、01背包问题 问题描述: 有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。 朴素01背包 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值 状态转移 1) 选第i个物品:f[i,j] = f

    2024年02月06日
    浏览(36)
  • 背包~~~~~~~~~3478:【例86.3】 完全背包问题

    【题目描述】 设有n�种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M�,今从n�种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M�,而价值的和为最大。 【输入】 第一行:两个整数,M�(背包

    2024年01月18日
    浏览(31)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(33)
  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(48)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(41)
  • 动态规划:完全背包问题

    ACwing #3. 完全背包问题 完全背包问题和01背包问题很相似。 01背包问题每个物品只能选一个,而完全背包问题每个物品可以选无限次。 DP问题的关键是找到状态转移方程: ①定义f[i][j]表示从前 i 个物品中选择,体积为 j 的时候的最大价值。 ②那么转移方程f[i][j] = max(f[i - 1][j

    2023年04月19日
    浏览(42)
  • C++--完全背包问题

    1.【模板】完全背包_牛客题霸_牛客网 你有一个背包,最多能容纳的体积是V。 现在有n种物品,每种物品有任意多个,第i种物品的体积为vivi​ ,价值为wiwi​。 (1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满,求至多能装多大价值的物品? 输入描述: 第一

    2024年02月10日
    浏览(31)
  • 动态规划——完全背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 了解完全背包问题前可以先去看看01背包问题(良心正解),先了解这个基础问题会更有利于你了解下面的完全背

    2024年02月04日
    浏览(45)
  • 动态规划完全背包问题-java

    完全背包问题跟01背包问题思路大致一样,只不过对于物品的拿取次数不在限制,我们只需要考虑这点即可。 文章目录 前言 一、什么是完全背包问题? 二、问题模拟 1.样例数据 2.算法思路 三、代码如下 1.代码如下(示例): 2.读入数 3.代码运行结果 总结 完全背包问题跟

    2024年04月26日
    浏览(42)
  • 【算法宇宙——在故事中学算法】背包dp之完全背包问题

    学习者不灵丝相传,而自杖明月相反,子来此事却无得失。 尽管计算机是门严谨的学科,但正因为严谨,所以要有趣味才能看得下去。在笔者的前几篇算法类文章中,都采用了以小故事作为引入的方式来介绍算法,但在回看的时候发现学术味还是太浓了,完全没有想看下去的

    2023年04月20日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包