动态规划的使用方法——01背包问题
问题主题：著名的01背包问题
问题说明：
重量和价值分别为wi、vi的有n个。 现在，从这些东西中选出总重量在w以下的东西，在所有的筛选方案中求出价值的最大值。
限制条件：
1=N=100
1=wi，vi=100
1=wi=10000
示例：
输入
N=4
w [ n ]={ 2，1，3，2 }
v [ n ]={ 3，2，4，2 }
输出功率
w=5(0(选择0、1、3号) ) ) )。
【解法1】
解决问题的分析：
常规递归方法查找每个项目是否在背包中
程序实现：
C
#包含
#包含
#包含
#include 'iostream '
using namespace std；
const int N=4；
const int W=5；
int weight [ n ]={ 2，1，3，2 }；
intvalue [ n ]={ 3，2，4，2 }；
intsolve(intI，int residue ) )。
{
int result=0；
if(I=n ) )
返回结果；
weight [ I ] residue ) )
result=solve(I1，residue )；
else
{
result=max(solve(I1，residue )，solve (i1 )，residue-weight[i] ) value[i] )；
}
}
int main ()。
intresult=solve(0，w )；
cout result endl；
返回0；
}
【解法2】
解决问题的分析：
在记录和重用结果的动态规划方法中，上述递归方法中重复计算较多，效率不高。 我们可以记录每次的计算结果，下次使用时直接去取，提高效率
程序实现：
C
#包含
#包含
#包含
#include 'iostream '
using namespace std；
const int N=4；
const int W=5；
int weight [ n ]={ 2，1，3，2 }；
intvalue [ n ]={ 3，2，4，2 }；
int record[N][W]；
void init () )
{
for(intI=0； i N； I )
{
for(intj=0； j W； j )
{
record[i][j]=-1；
}
}
}
intsolve(intI，int residue ) )。
{
if(-1！=record[i][residue] )
return record[i][residue]；
int result=0；
if(I=n ) )
返回结果；
weight [ I ] residue ) )
{
record[i 1][residue]=solve(i 1，residue )；
}
else
{
result=max(solve(I1，residue )，solve (i1 )，residue-weight[i] ) value[i] )；
}
返回记录[ i1 ] [ residue ]=result；
}
int main ()。
init (；
intresult=solve(0，w )；
cout result endl；
返回0；
}
Java
包绿色；
//*
* user :微信号
* Date: 14-1-21
* Time:下午5:13
*/
公共类密钥{
private int maxWeight；
private int [ ] [ ]记录；
private Stuff[] stuffs；
publicknapsack(stuff[]stuffs，int maxWeight ) {
this.stuffs=stuffs；
this.maxWeight=maxWeight；
int n=stuffs.length 1；
int m=maxWeight 1；
record=new int[n][m]；
for(intI=0； i n； I ) {
for(intj=0； j m； j ) {
record[i][j]=-1；
}
}
}
公共解决方案(inti，int residue ) {
record [ I ] [ residue ]0) {
return record[i][residue]；
}
输入结果；
if(I=stuffs.length ) {
返回0；
}
stuffs [ I ].get weight ) residue ) {
result=solve(I1，residue )；
} else {
result=math.max(solve(I1，residue )，
solve(I1，residue - stuffs[i].getWeight () ) stuffs[i].getValue )；
}
record[i][residue]=result；
返回结果；
}
publicstaticvoidmain (string args [ ] ) {
Stuff stuffs[]={
new stuff (2，3 )为，
新软件(1，2 )、
新软件(3，4 )、
新的stuff (2，2 ) )。
(；
knapsack knapsack=new knapsack (stuffs，5 )；
int result=knapsack.solve (0，5 )；
system.out.println(result )；
}
}
class Stuff{
权限输入权重；
私有输入值；
公共安全(int weight，int value ) {
this.weight=weight；
this.value=value；
}
intgetweight(}
返回权重；
}
voidsetweight (输入权重)。
this.weight=weight；
}
int getValue () }
返回值；
}
voidsetvalue(intvalue ) {
this.value=value；
}
}
算法复杂性：
时间复杂度o(NW ) )。