具有营销型网站的公司,贵阳专用网站建设,dedecms口腔医院类网站模板 织梦网站模板,总做总结 网站维护的收获1.【模板】完全背包_牛客题霸_牛客网 你有一个背包#xff0c;最多能容纳的体积是V。 现在有n种物品#xff0c;每种物品有任意多个#xff0c;第i种物品的体积为vivi ,价值为wiwi。 #xff08;1#xff09;求这个背包至多能装多大价值的物品#xff1f; #xff0…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*2596若要求恰好装满只能装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
输出0class Solution {
public:int coinChange(vectorint coins, int amount) {int ncoins.size();vectorint dp(amount1);//创建dp表for(int i1;iamount;i) dp[i]0x3f3f3f3f;//初始化寻找最小值for(int i1;in;i){for(int jcoins[i-1];jamount;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
解释有四种方式可以凑成总金额
55
5221
52111
511111示例 2 输入amount 3, coins [2]
输出0
解释只用面额 2 的硬币不能凑成总金额 3 。示例 3 输入amount 10, coins [10]
输出1class Solution {
public:int change(int amount, vectorint coins) {int ncoins.size();vectorint dp(amount1);dp[0]1;//初始化for(int i1;in;i){for(int jcoins[i-1];jamount;j){dp[j]dp[j-coins[i-1]];//动态转移方程}}return dp[amount];//返回值}
};
4.完全平方数 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 示例 1 输入n 12
输出3
解释12 4 4 4 示例 2 输入n 13
输出2
解释13 4 9 class Solution {
public:int numSquares(int n) {int msqrt(n);vectorint dp(n1,0x3f3f3f3f);//初始化dp[0]0;for(int i1;im;i){for(int ji*i;jn;j){dp[j]min(dp[j],dp[j-i*i]1);//动态转移方程}}return dp[n]; }
};
