关键词：
动态规划问题结题思路：
模板题链接：
01背包
思路：
定义状态表示函数 f ( i , j ) ： f(i,j)： f(i,j)：
j空间大小的背包，在对（1 ~ i）号物品做出选择后，背包能装下的最大价值。
所以产生了如下集合。
在选择i号物品的情况下 :
f
(
i
,
j
)
f(i,j)
f(i,j)的值就为
f
(
i
−
1
,
j
−
v
[
i
]
)
+
w
[
i
]
f(i-1,j-v[i])+w[i]
f(i−1,j−v[i])+w[i]
在不选择i号物品的情况下 :
f
(
i
,
j
)
f(i,j)
f(i,j)的值就为
f
(
i
−
1
,
j
)
f(i-1,j)
f(i−1,j)
最终的最优解就为
f
(
物
品
数
量
,
背
包
容
量
)
f(物品数量,背包容量)
f(物品数量,背包容量)
代码：
#include<iostream>
using namespace std;
const int N = 1e3+5;
int w[N],v[N],f[N][N];
int main()
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
//将这轮for循环转换为从后往前，就可以将二维数组f转换为一维数组f。
f[i][j]=f[i-1][j];//不放i号物品
//可以放i号物品的情况下的最大值
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
cout<<f[n][m]<<endl;
return 0;
完全背包
思路:
思路同01背包，完全背包和01背包不同的一点是，01背包每个物品只能取一次，而完全背包一个物品可以取多次。所以
f
(
i
,
j
)
f(i,j)
f(i,j)需要更改表示方式为：
在选择k个i号物品的情况下 :
f
(
i
,
j
)
=
M
a
x
(
f
(
i
−
1
,
j
)
，
f
(
i
−
1
,
j
−
v
[
i
]
)
+
w
[
i
]
，
f
(
i
−
1
,
j
−
2
v
[
i
]
)
+
2
w
[
i
]
，
.
.
.
，
f
(
i
−
1
,
j
−
k
v
[
i
]
)
+
k
w
[
i
]
)
f(i,j)=Max(f(i-1,j)，f(i-1,j-v[i])+w[i]，f(i-1,j-2v[i])+2w[i]，...，f(i-1,j-kv[i])+kw[i])
f(i,j)=Max(f(i−1,j)，f(i−1,j−v[i])+w[i]，f(i−1,j−2v[i])+2w[i]，...，f(i−1,j−kv[i])+kw[i])
同时可以观察发现：
f
(
i
,
j
−
v
[
i
]
)
=
M
a
x
(
f
(
i
−
1
,
j
−
v
[
i
]
)
，
f
(
i
−
1
,
j
−
2
v
[
i
]
)
+
2
w
[
i
]
，
f
(
i
−
1
,
j
−
3
v
[
i
]
)
+
3
w
[
i
]
，
.
.
.
，
f
(
i
−
1
,
j
−
k
v
[
i
]
)
+
k
w
[
i
]
)
f(i,j-v[i])=Max(f(i-1,j-v[i])，f(i-1,j-2v[i])+2w[i]，f(i-1,j-3v[i])+3w[i]，...，f(i-1,j-kv[i])+kw[i])
f(i,j−v[i])=Max(f(i−1,j−v[i])，f(i−1,j−2v[i])+2w[i]，f(i−1,j−3v[i])+3w[i]，...，f(i−1,j−kv[i])+kw[i])
将上面两式合并，得;
f
(
i
,
j
)
=
M
a
x
(
f
(
i
−
1
,
j
)
，
f
(
i
,
j
−
v
[
i
]
)
+
w
[
i
]
)
f(i,j)=Max(f(i-1,j)，f(i,j-v[i])+w[i])
f(i,j)=Max(f(i−1,j)，f(i,j−v[i])+w[i])
上式和01背包的区别只在后一项上，01背包是只和i-1的状态有关，而完全背包不但和i-1的状态有关，也与i的状态有关。
代码
#include<iostream>
using namespace std;
const int N = 1e3+5;
int f[N],w[N],v[N];
int n,m;
int main()
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
多重背包
思路：
如果强行按照完全背包思想进行枚举，在有1000个物品以上时，往往会浪费大量时间。这时候，就需要一个操作，将O(n)的复杂度降低到O(logN)。这时就用到了多重背包的二进制转换思想。
假设有一个物品可以取S次，则S一定满足
S
=
111...1
+
C
S=111...1+C
S=111...1+C
其中一共有
⌊
l
o
g
2
(
S
)
⌋
\\lfloor log_2(S) \\rfloor
⌊log2(S)⌋个1，C为一个常数。所以对于任意一个小于S的数s’,都可以通过在
2
0
,
2
1
,
.
.
.
2
k
\\2^0,2^1,...2^k\\
20,21,...2k中取任意一个数和C的组合实现。
于是，一个可以取S次的物品就被拆分成了
⌊
l
o
g
2
(
S
)
⌋
+
1
\\lfloor log_2(S) \\rfloor+1
⌊log2(S)⌋+1个物品。（+1是为了考虑C）
对所有物品经过这些操作以后，就完了问题的转换。将问题转换为了一个标准的01背包问题。
代码：
#include<iostream>
using namespace std;
const int N = 1005,M = 2005;
int v[12005],w[12005],f[2005];
int n,m,cnt;
int main()
cin>>n>>m;
for(int i=0;i<n;i++)
//转换物品
int a,b,s;//体积，权重，最大数量
cin>>a>>b>>s;
int k=1;
while(k<=s)
cnt++;
w[cnt]=k*b;
v[cnt]=k*a;
s-=k;
k<<=1;
if(s)
cnt++;
w[cnt]=s*b;
v[cnt]=s*a;
//01背包的解法
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
组合背包
思路：
同完全背包问题，只是将一个数去很多次，转换为了多个数取一次。
代码：
#include<iostream>
using namespace std;
const int N=105;
int w[N][N],v[N][N],s[N],f[N];
int main()
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
for(int i=1;i<=n;i++)//第几组
for(int j=m;j>0;j--)//背包大小
for(int k=1;k<=s[i];k++)//枚举i组的物品
if(v[i][k]<=j)
f[j]=max(f[j],f[j-v[i][k动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情
动态规划之背包问题-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... 查看详情
动态规划_背包问题(代码片段)
背包问题：问题描述有(n)件物品，每件物品的体积为(V_i),价值为(W_i),有一个体积为(V)的背包，求总体积不大于(V)的所有物品总价值最大是多少01背包问题:每件物品只能用一次状态表示：(dp[i][j])集合：所有选法条件：仅从前(i)个... 查看详情
0-1背包问题_动态规划(代码片段)
...sp;普通背包问题可以用贪心来解决，而0-1背包问题只能靠动态规划来做，而且在我们平时的做题中经常会遇到0-1背包问题的变形，所以有必要牢牢掌握0-1背包问题的思想和解题思路。根据下面的图更可以找到应该选那些背包下面... 查看详情
多重背包
<spanstyle="color:#3333ff;">/*__________________________________________________________________________________________________*copyright:GrantYuan**algorithm:多重背包**time:2014.7.18**____________ 查看详情
动态规划多重背包问题(代码片段)
说明前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。这个背包，听起来就很麻烦的样子。别慌，只要你理解了前面的两种背包问题，拿下多重背包简直小菜一碟。如果没有看过前两篇01背包和完... 查看详情
01背包完全背包多重背包分组背包总结
文章目录一、01背包问题二、完全背包问题三、多重背包问题四、分组背包一、01背包问题n个物品，每个物品的重量是，价值是，背包的容量是若每个物品最多只能装一个，且不能超过背包容... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
poj_1276_多重背包
#include<iostream>#include<string.h>usingnamespacestd;/*********************多重背包问题************************///n=a0•2k+a1•2k−1+…+ak−1•21+ak•20，其中a0=1，a1 查看详情
hdu_2191_多重背包
http://acm.hdu.edu.cn/showproblem.php?pid=2191 简单多重背包题。 #include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intn,m,p[105],h[105],c[105],ans[105];intmain(){ 查看详情
hdu_3732_(多重背包)
AhuiWritesWordTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):2915 AcceptedSubmission(s):1036ProblemDescription 查看详情
p1450[haoi2008]硬币购物（完全背包+容斥）(代码片段)
P1450[HAOI2008]硬币购物暴力做法：每次询问跑一遍多重背包。考虑正解其实每次跑多重背包都有一部分是被重复算的，浪费了大量时间考虑先做一遍完全背包算出$f[i]$表示买价值$i$东西的方案数蓝后对每次询问价值$t$，减去不合法... 查看详情
01背包
<spanstyle="color:#3333ff;">/*__________________________________________________________________________________________________*copyright:GrantYuan**algorithm:01背包**time:2014.7.18**__ 查看详情
完全背包详解_动态规划(代码片段)
...r(inti=1;i<=n;i++)cin>>w[i]>>v[i];memset(dp,0,sizeof(dp));/*动态规划计算*/for(inti=1;i<=n;i++)for(intj=1;j<=W;j++)for(i 查看详情
单调队列优化多重背包
记得有一个经典的问题： 有一个容量为$V$的背包，和$n$种物品。第$i$种物品的重量为$w_{i}$，价值为$v_{i}$，数量为$c_{i}$。问背包中装的物品的最大价值和为多少。Subtask1$1leqslantnleqslant100,1leqslantVleqslant1000,1leqslantc_{i}leqslan... 查看详情
investment_完全背包
DescriptionJohnneverknewhehadagrand-uncle,untilhereceivedthenotary‘sletter.Helearnedthathislategrand-unclehadgatheredalotofmoney,somewhereinSouth-America,andthatJohnwastheonlyinheritor.Johndidnotneedt 查看详情
lightoj1231_多重背包
题目链接：http://lightoj.com/volume_showproblem.php?problem=1231题意：给你不同种类的硬币和个数，让你求组成面值为k的方法数1#include<algorithm>2#include<iostream>3#include<cstring>4#include<cstdlib>5#include< 查看详情