长沙在线建站模板,酷炫的网站模板免费下载,网站建设开题报告设计,邵阳建设网站的公司完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品都有无限个#xff08;也就是可以放入背包多次#xff09;#xff0c;求解将哪些物品装入背包里物品价值总和最大。 例子#xff1a; 背包可容纳重…完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品都有无限个也就是可以放入背包多次求解将哪些物品装入背包里物品价值总和最大。 例子 背包可容纳重量 W 6
物品重量w价值v123241335412543二维数组
for (int i 1; i N 1; i) {for (int j 0; j W 1; j) {if (j weight[i-1]) {dp[i][j] dp[i - 1][j];} else {//第 i 个物品放入剩余背包容量为 j - weight[i - 1]总价值为前 i 件物品中放入背包中的价值 第 i 件物品的价值dp[i][j] max(dp[i - 1][j], dp[i][j - weight[i - 1]] value[i - 1]);}}
}-012345600000000100336692003366930035681040246810125024681012
一维数组
for (int i 1; i N 1; i) { // i 从 1 开始的所以物品对应下标后面是 i - 1for (int j weight[i - 1]; j W 1; j) { // 正序完全背包物品可以多次放入dp[j] max(dp[j], dp[j - weight[i - 1]] value[i - 1]);}
}52. 携带研究材料
卡码网 52. 携带研究材料 题目描述 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。 小明的行李箱所能承担的总重量为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。 输入描述 第一行包含两个整数NV分别表示研究材料的种类和行李空间 接下来包含 N 行每行两个整数 wi 和 vi代表第 i 种研究材料的重量和价值 输出描述 输出一个整数表示最大价值。 输入示例 4 5 1 2 2 4 3 4 4 5 输出示例 10 提示信息 第一种材料选择五次可以达到最大值。 数据范围 1 N 10000; 1 V 10000; 1 wi, vi 10^9. #include iostream
#include vector
using namespace std;int package(int m, int n, vectorvectorint stuff) {vectorint dp(n 1);for (int i 1; i m 1; i) {for (int j stuff[i - 1][0]; j n 1; j) { // 正序完全背包物品可以多次放入dp[j] max(dp[j], dp[j - stuff[i - 1][0]] stuff[i - 1][1]);}}return dp[n];
}
int main() {int m; // 材料种类int n; // 行李空间cin m n;vectorvectorint stuff(m, vectorint(2)); for (int i 0; i m; i) {cin stuff[i][0] stuff[i][1];}int res package(m, n, stuff);cout res endl;return 0;
}518. 零钱兑换 II
518. 零钱兑换 II 给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 给定背包容量装满背包有多少种方法每件物品有无限个
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1);dp[0] 1;for (int i 1; i coins.size() 1; i) {for (int j coins[i - 1]; j amount 1; j) {dp[j] dp[j] dp[j - coins[i - 1]];}}return dp[amount];}
};377. 组合总和 Ⅳ
377. 组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 顺序不同的序列被视作不同的组合。 给定背包容量j装满背包有多少种不同的排列dp[j]每件物品有无限个
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1);dp[0] 1;for (int j 0; j target 1; j) {/ 遍历背包for (int i 0; i nums.size(); i) { // 遍历物品 // 终于把我从二维数组dp继承过来的 i 1 给改了if(j nums[i] dp[i] INT_MAX - dp[i - nums[j]]) { // 用例有溢出dp[j] dp[j - nums[i]];}}}return dp[target];}
};如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
70. 爬楼梯 进阶
卡码网57. 爬楼梯 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢 注意给定 n 是一个正整数。 输入描述 输入共一行包含两个正整数分别表示n, m 输出描述 输出一个整数表示爬到楼顶的方法数。 输入示例 3 2 输出示例 3 提示信息 数据范围 1 m n 32; 当 m 2n 3 时n 3 这表示一共有三个台阶m 2 代表你每次可以爬一个台阶或者两个台阶。 此时你有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶 1 阶 2 阶 2 阶 1 阶 #include iostream
#include vector
using namespace std;int climbStairs(int n, int m) {// 背包容量为 n 1;// 物品为1, 2, 3, ... ,m // 给定背包容量装满背包有多少种不同的**排列**每件物品有无限个vectorint dp(n 1);dp[0] 1;for (int j 0; j n 1; j) { // 遍历背包for (int i 1; i m; i) { // 遍历物品if(j i) { dp[j] dp[j - i];}}}return dp[n];
}int main() {int n, m;cin n m;cout climbStairs(n, m) endl;return 0;
}
