关键词：
01背包
问题描述
已知：有一个容量为 V 的背包和 N 件物品，第 i 件物品的重量是 weight[ i ]，收益是 cost[ i ]。
限制：每种物品只有一件，可以选择放或者不放
问题：在不超过背包容量的情况下，最多能获得多少价值或收益
相似问题：在恰好装满背包的情况下，最多能获得多少价值或收益
这里，我们先讨论在不超过背包容量的情况下，最多能获得多少价值或收益。
基本思路
01背包的特点：每种物品只有一件，可以选择放或者不放
状态转移方程：f[ i ][ v ] = max( f[ i - 1 ][ v ] , f[ i - 1 ][ v - weight[ i ] ] + cost[ i ] )
代码
1 #include <iostream> 2 using namespace std; 3 4 const int N = 3;//物品个数 5 const int V = 5;//背包最大容量 6 int weight[N + 1] = 0,3,2,2;//物品重量 7 int value[N + 1] = 0,5,10,20;//物品价值 8 9 int f[N + 1][V + 1] = 0; 10 11 int Max(int x,int y) 12 13 return x > y ? x : y; 14 15 16 /* 17 目标：在不超过背包容量的情况下，最多能获得多少价值 18 19 子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值 20 21 状态转移方程:f[i][j] = maxf[i - 1][j],f[i - 1][j - weight[i]] + value[i] 22 23 初始化:f数组全设置为0 24 */ 25 int Knapsack() 26 27 //初始化 28 memset(f,0,sizeof(f)); 29 //递推 30 for (int i = 1;i <= N;i++) //枚举物品 31 32 for (int j = 0;j <= V;j++) //枚举背包容量 33 34 f[i][j] = f[i - 1][j]; 35 if (j >= weight[i]) 36 37 f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]); 38 39 40 41 return f[N][V]; 42 43 44 int main() 45 46 cout<<Knapsack()<<endl; 47 return 1; 48
1 #include <iostream> 2 using namespace std; 3 4 const int N = 3;//物品个数 5 const int V = 5;//背包最大容量 6 int weight[N + 1] = 0,3,2,2;//物品重量 7 int value[N + 1] = 0,5,10,20;//物品价值 8 9 int f[V + 1] = 0; 10 11 int Max(int x,int y) 12 13 return x > y ? x : y; 14 15 16 /* 17 目标：在不超过背包容量的情况下，最多能获得多少价值 18 19 子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值 20 21 状态转移方程:f[j] = maxf[j],f[j - weight[i]] + value[i] 22 23 初始化:f数组全设置为0 24 */ 25 int Knapsack() 26 27 //初始化 28 memset(f,0,sizeof(f)); 29 //递推 30 for (int i = 1;i <= N;i++) //枚举物品 31 32 for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界，j下限为 weight[i] 33 34 f[j] = Max(f[j],f[j - weight[i]] + value[i]); 35 36 37 return f[V]; 38 39 40 int main() 41 42 cout<<Knapsack()<<endl; 43 return 1; 44
恰好装满
使用二维数组f[i][v]存储中间状态，其中第一维表示物品，第二维表示背包容量；初始化时，除了f[i][0] = 0（第一列）外，其他全为负无穷。
1 #include <iostream> 2 using namespace std; 3 4 const int MinNum = 0x80000000; 5 6 const int N = 3;//物品个数 7 const int V = 5;//背包最大容量 8 int weight[N + 1] = 0,3,2,2;//物品重量 9 int value[N + 1] = 0,5,10,20;//物品价值 10 11 int f[N + 1][V + 1] = 0; 12 13 int Max(int x,int y) 14 15 return x > y ? x : y; 16 17 18 /* 19 目标：在恰好装满背包的情况下，最多能获得多少价值 20 21 子问题状态:f[i][j]:表示前i件物品放入容量为j的背包得到的最大价值 22 23 状态转移方程:f[i][j] = maxf[i - 1][j],f[i - 1][j - weight[i]] + value[i] 24 25 初始化:f数组全设置为0 26 */ 27 int Knapsack() 28 29 //初始化 30 for (int i = 0;i <= N;i++) //枚举物品 31 32 for (int j = 0;j <= V;j++) //枚举背包容量 33 34 f[i][j] = MinNum; 35 36 37 for (int i = 0;i <= N;i++) 38 39 f[i][0] = 0;//背包容量为0时为合法状态 40 41 //递推 42 for (int i = 1;i <= N;i++) //枚举物品 43 44 for (int j = 1;j <= V;j++) //枚举背包容量 45 46 f[i][j] = f[i - 1][j]; 47 if (j >= weight[i]) 48 49 f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i]); 50 51 52 53 return f[N][V]; 54 55 56 int main() 57 58 cout<<Knapsack()<<endl;//输出25 59 return 1; 60
1 #include <iostream> 2 using namespace std; 3 4 const int MinNum = 0x80000000;//int最小的数 5 6 const int N = 3;//物品个数 7 const int V = 5;//背包最大容量 8 int weight[N + 1] = 0,3,2,2;//物品重量 9 int value[N + 1] = 0,5,10,20;//物品价值 10 11 int f[V + 1] = 0; 12 13 int Max(int x,int y) 14 15 return x > y ? x : y; 16 17 18 /* 19 目标：在恰好装满背包容量的情况下，最多能获得多少价值 20 21 子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值 22 23 状态转移方程:f[j] = maxf[j],f[j - weight[i]] + value[i] 24 25 初始化:f数组全设置为0 26 */ 27 int Knapsack() 28 29 //初始化 30 for (int i = 0;i <= V;i++) 31 32 f[i] = MinNum; 33 34 f[0] = 0;//只有背包容量为0时才是合法状态，由合法状态组成的结果才是合法的 35 36 //递推 37 for (int i = 1;i <= N;i++) //枚举物品 38 39 for (int j = V;j >= weight[i];j--) //枚举背包容量,防越界，j下限为 weight[i] 40 41 f[j] = Max(f[j],f[j - weight[i]] + value[i]); 42 43 44 return f[V]; 45 46 47 int main() 48 49 cout<<Knapsack()<<endl;//输出25 50 return 1; 51
完全背包
问题描述
已知：有一个容量为 V 的背包和 N 件物品，第 i 件物品的重量是 weight[ i ]，收益是 cost[ i ]。
条件：每种物品都有无限件，能放多少就放多少。
问题：在不超过背包容量的情况下，最多能获得多少价值或收益。
基本思路
方法有拆分物品、二进制转换等，但都太慢。
只需将逆序枚举的01背包改成顺序枚举即可。
代码
1 #include <iostream> 2 #include <vector> 3 #include <assert.h> 4 using namespace std; 5 const int N = 3; 6 const int V = 5;//5 7 int weight[N + 1] = 0,3,2,2; 8 int Value[N + 1] = 0,5,10,20; 9 10 int f[N + 1][V + 1] = 0; 11 12 int Completeknapsack() 13 14 //初始化 15 for (int i = 0;i <= N;i++) 16 17 f[i][0] = 0; 18 19 for (int v = 0;v <= V;v++) 20 21 f[0][v] = 0; 22 23 for (int i = 1;i <= N;i++) 24 25 for (int v = weight[i];v <= V;v++) 26 27 f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]); 28 29 30 return f[N][V]; 31 32 33 int main() 34 35 cout<<Completeknapsack()<<endl; 36 return 1; 37
1 include <iostream> 2 using namespace std; 3 const int N = 3; 4 const int V = 5;//5 5 int weight[N + 1] = 0,3,2,2; 6 int Value[N + 1] = 0,5,10,20; 7 8 int f[V + 1] = 0; 9 10 int Completeknapsack() 11 12 f[0] = 0; 13 for (int i = 1;i <= N;i++) 14 15 for (int v = weight[i];v <= V;v++) 16 17 f[v] = max(f[v],f[v - weight[i]] + Value[i]); 18 19 20 return f[V]; 21 22 int main() 23 24 cout<<Completeknapsack()<<endl; 25 return 1; 26
from 远航之曲
01背包问题复习(代码片段)
01背包问题复习518.零钱兑换IIeasyclassSolution//amount=5,coins=[1,2,5]问有多少种方法用coins凑成amountpublicintchange(intamount,int[]coins)int[]dp=newint[amount+1];dp[0]=1;for(intval:coins)for(inti= 查看详情
背包复习(代码片段)
01背包问题描述已知：有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。限制：每种物品只有一件，可以选择放或者不放问题：在不超过背包容量的情况下，最多能获得多少价值或收益相似问题：在恰好... 查看详情
dp复习01背包ovo(代码片段)
水题10s切得pj-的那种QAQ P1048采药1#include<cstdio>2#include<iostream>3usingnamespacestd;4constintsz=1010;5intdp[sz],val[sz],tim[sz];6intt,m;7intmain()8scanf("%d%d",&t,&m);9for(inti=1; 查看详情
01背包问题复习(代码片段)
01背包问题复习518.零钱兑换IIeasyclassSolution//amount=5,coins=[1,2,5]问有多少种方法用coins凑成amountpublicintchange(intamount,int[]coins)int[]dp=newint[amount+1];dp[0]=1;for(intval:coins)for(inti=val;i<=amount;i++)//如果是背包里的物... 查看详情
01背包与完全背包（dp复习）(代码片段)
01背包和完全背包都是dp入门的经典，我的dp学的十分的水，借此更新博客的机会回顾一下01背包：给定总容量为maxv的背包，有n件物品，第i件物品的的体积为w[i],价值为v[i],问如何选取才能是背包内的物品价值总和最大。stdin：5123... 查看详情
复习动规(代码片段)
...规划。 单调队列优化dp第一道，宝物筛选。一道多重背包优化题。如果用二进制优化很好做，但时间复杂度是O(nW*logm)。单调队列优化做法如下：首先做出普通的多重背包的转移方程：f[j]=maxf[j-w*k]+v*k，w为重量，v为价值。使... 查看详情
iloveexamhdu-6968(代码片段)
...数目不能超过p，问所有达到的最大分数题解：01背包有两个背包转移过程首先不用考虑挂科的事，我们将试题按照名称排序 查看详情
算法复习——背包dp
1.01背包 二维递推式子： 代码： for(i=1;i<=n;i++)for(x=m;x>=1;x--)if(x>=w[i])f[i][x]=max(f[i-1][x-w[i]]+c[i],f[i-1][x]);elsef[i][x]=f[i-1][x];printf("%d",f[n][m]);// 查看详情
codevs3269混合背包（复习混合背包）
传送门【题目大意】给出物品的数量。-1为无限个。【思路】混合背包....【code】#include<iostream>#include<cstdio>#include<cstdlib>usingnamespacestd;intw[100000],v[100000],c[10000],dp[20000000];intmain(){intvv,n;scanf("% 查看详情
背包问题(代码片段)
复健\\(Day1\\)今天复习基础背包问题，在\\(ACWing\\)上使用挑战模式去打模板，提高打代码速度\\(01\\)背包解决每种物品只有一样的情况时间复杂度\\(O(nV)\\)，空间复杂度优化后为\\(O(V))\\)空间优化的代码中体积一维从后往前更新，... 查看详情
悼念512汶川大地震遇难同胞——珍惜现在，感恩生活（复习多重背包）
...量，价格，袋数。求购买大米的最终重量。【思路】多重背包。【复习】多重背包特点。题目 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品... 查看详情
背包问题(代码片段)
目录背包问题来源动态规划的关键点No.1：01背包问题分析codeNo.2：完全背包问题分析方法一code方法二codeNo.3：多重背包(未完待续)背包问题来源完全基于中山纪念中学宋新波ppt的一次复习动态规划的关键点最优化原理子问题最优... 查看详情
piggy-bank（复习完全背包）
...和重量。求装满储钱罐时最小能得到多少钱。题解：完全背包变形。因为要求最小一开始赋值大数。code: #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intw1,w2,wi,t,k,f 查看详情
算法设计与分析期中考试复习：代码和经典题目分治二分动态规划（未完待续）(代码片段)
...：矩阵相乘，数塔，最长公共子序列，0-1背包。快速排序思想： 查看详情
dp复习 背包[礼物]
【问题描述】人生赢家老王在网上认识了一个妹纸,然后妹纸的生日到了，为了表示自己的心意，他决定送她礼物。可是她喜爱的东西特别多，然而他的钱数有限，因此他想知道当他花一定钱数后剩余钱数无法再购买任何一件剩... 查看详情
背包0-1背包与完全背包一维数组实现(代码片段)
背包问题很经典了，《背包问题九讲》讲的非常详细，建议看一看。在这里，我想给出0-1背包和完全背包压缩空间后的实现，即只要一维数组。0-1背包，与完全背包仅仅只是内循环的次序不同，故而代码基本相同。希望可以帮的... 查看详情
背包问题(代码片段)
背包问题分类：0-1背包（每种物品只有一个）完全背包（每种物品无限多）多重背包（每种物品Mi个，0-1背包算是多重背包的特殊情况）混合背包。。。解决此类问题主要将其转化为0-1背包的问题&#x... 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情