关键词：
在hihocoder上面的题目中看到的这个问题，总结一下。先看01背包问题。
01背包问题：一个背包总容量为V，现在有N个物品，第i个 物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
看到这个问题，可能会想到贪心算法，但是贪心其实是不对的。例如最少硬币找零问题，要用动态规划。动态规划思想就是解决子问题并记录子问题的解，这样就不用重复解决子问题了。
动态规划先找出子问题，我们可以这样考虑：在物品比较少，背包容量比较小时怎么解决？用一个数组f[i][j]表示，在只有i个物品，容量为j的情况下背包问题的最优解，那么当物品种类变大为i+1时，最优解是什么？第i+1个物品可以选择放进背包或者不放进背包（这也就是0和1），假设放进背包（前提是放得下），那么f[i+1][j]=f[i][j-weight[i+1]+value[i+1]；如果不放进背包，那么f[i+1][j]=f[i][j]。
这就得出了状态转移方程：
f[i+1][j]=max(f[i][j],f[i][j-weight[i+1]+value[i+1])。
可以写出代码测试：
#include<iostream>
using namespace std;
#define V 1500
unsigned int f[10][V];//全局变量，自动初始化为0
unsigned int weight[10];
unsigned int value[10];
#define max(x,y) (x)>(y)?(x):(y)
int main()
int N,M;
cin>>N;//物品个数
cin>>M;//背包容量
for (int i=1;i<=N; i++)
cin>>weight[i]>>value[i];
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
if (weight[i]<=j)
f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]);
else
f[i][j]=f[i-1][j];
cout<<f[N][M]<<endl;//输出最优解
在hihocoder上面还讲到可以进一步优化内存使用。上面计算f[i][j]可以看出，在计算f[i][j]时只使用了f[i-1][0……j]，没有使用其他子问题，因此在存储子问题的解时，只存储f[i-1]子问题的解即可。这样可以用两个一维数组解决，一个存储子问题，一个存储正在解决的子问题。
再进一步思考，计算f[i][j]时只使用了f[i-1][0……j]，没有使用f[i-1][j+1]这样的话，我们先计算j的循环时，让j=M……1，只使用一个一维数组即可。
for i=1……N
for j=M……1
f[j]=max(f[j],f[j-weight[i]+value[i])
#include<iostream>
using namespace std;
#define V 1500
unsigned int f[V];//全局变量，自动初始化为0
unsigned int weight[10];
unsigned int value[10];
#define max(x,y) (x)>(y)?(x):(y)
int main()
int N,M;
cin>>N;//物品个数
cin>>M;//背包容量
for (int i=1;i<=N; i++)
cin>>weight[i]>>value[i];
for (int i=1; i<=N; i++)
for (int j=M; j>=1; j--)
if (weight[i]<=j)
f[j]=max(f[j],f[j-weight[i]]+value[i]);
cout<<f[M]<<endl;//输出最优解
在看完01背包问题，再来看完全背包问题： 一个背包总容量为V，现在有N个物品，第i个 物品体积为weight[i]，价值为value[i]，每个物品都有无限多件，现在往背包里面装东西，怎么装能使背包的内物品价值最大？
对比一下，看到的区别是，完全背包问题中，物品有无限多件。往背包里面添加物品时，只要当前背包没装满，可以一直添加。那么状态转移方程为：
f[i+1][j]=max(f[i][j-k*weight[i+1]]+k*value[i+1])，其中0<=k<=V/weight[i+1]
使用内存为一维数组，伪代码
for i=1……N
for j=1……M
f[j]=max(f[j],f[j-weight[i]+value[i])
和01背包问题唯一不同的是j是从1到M。01背包问题是在前一个子问题（i-1 种物品）的基础上来解决当前问题（i 种物品），向i-1种物品时的背包添加第i种物品；而完全背包问题是在解决当前问题（i种物品），向i种物品时的背包添加第i种物品。代码如下：
#include<iostream>
using namespace std;
#define V 1500
unsigned int f[V];//全局变量，自动初始化为0
unsigned int weight[10];
unsigned int value[10];
#define max(x,y) (x)>(y)?(x):(y)
int main()
int N,M;
cin>>N;//物品个数
cin>>M;//背包容量
for (int i=1;i<=N; i++)
cin>>weight[i]>>value[i];
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
if (weight[i]<=j)
f[j]=max(f[j],f[j-weight[i]]+value[i]);
cout<<f[M]<<endl;//输出最优解
01背包问题和完全背包问题(代码片段)
...coder上面的题目中看到的这个问题，总结一下。先看01背包问题。01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的... 查看详情
acwing（基础）---01背包和完全背包多重背包问题(代码片段)
初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候... 查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
动态规划--01背包问题和完全背包问题(代码片段)
动态规划的01背包问题和完全背包问题模板01背包问题模板：//01背包问题#include<stdio.h>#include<algorithm>usingnamespacestd;constintmaxn=100;//物品的最大件数constintmaxv=1000;//V的上限intw[maxn],c[maxn],dp[maxv];intmain()//边界for(intv=0;v<=V;v++)d... 查看详情
背包问题专栏（01，完全，多重）(代码片段)
...的模板是套用了A.S.KirigiriKyouko的模板。请dalao见谅一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和... 查看详情
动态规划——完全背包拓展问题(代码片段)
完全背包问题给定你一个固定的背包容量capacity，和两个数组weigth,value，分别表示下标为i的物品的重量和价值，每件物品有无数件，问你背包能够存放下物品的最大价值是多少？这与之前的01背包极其拓展问题... 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
动态规划多重背包问题(代码片段)
说明前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和完... 查看详情
第二讲完全背包问题(对背包九讲的学习)(代码片段)
学习自:背包九讲题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路:完全背包和01... 查看详情
动态规划2——完全背包问题解析(代码片段)
完全背包问题描述有C种物品和一个容量为V的背包，每种物品都有无限件。第i件物品的体积是v[i]，价值是w[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。与之前的01背包不同的是，每个... 查看详情
动态规划2——完全背包问题解析(代码片段)
完全背包问题描述有C种物品和一个容量为V的背包，每种物品都有无限件。第i件物品的体积是v[i]，价值是w[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。与之前的01背包不同的是，每个... 查看详情
leetcode刷题（132）——完全背包问题思路理解(代码片段)
完全背包问题描述有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。... 查看详情
2.完全背包问题(代码片段)
完全背包问题是每件物品有无限个完全背包问题的状态表示和01背包问题一样dp[i][j]表示只看前i个物品，总体积<=j的最大价值状态计算： 按照第i个物品选了多少个来分 然后综合起来就是k是枚举的第i个物品的个数... 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划——完全背包拓展问题(代码片段)
完全背包问题给定你一个固定的背包容量capacity，和两个数组weigth,value，分别表示下标为i的物品的重量和价值，每件物品有无数件，问你背包能够存放下物品的最大价值是多少？这与之前的01背包极其拓展问题... 查看详情
完全背包问题(代码片段)
目录 一.什么是完全背包二.完全背包问题的里外层循环可以交换吗 三.题3.1求组合数3.2 求排列和3.3求最小值 一.什么是完全背包 完全背包问题一般是指：有N件物品和一个能背重量为W的背包，第i件物品的重... 查看详情