一、实验内容
1、实验题目
0/1背包问题：给定n 中物品和一个背包，物品i 的重量是wi ，价值是vi ，背包的容量为c 。
2、实验目的
（1）深刻理解并掌握动态规划算法的设计思想；
（2）利用动态规划方法设计背包问题算法，掌握动态规划法
的基本思想和算法设计的基本步骤。
3、实验要求
设计0/1背包问题的动态规划算法，要求输出背包内物品
的最大价值以及选入背包的物品种类。利用c++语言实现
算法，给出程序的正确运行结果。
4、算法设计思想
0/1背包为题可以看作是决策一个序列（x1，x2······xn ），对任何一个变量xi 的 决策是决定xi=1还是xi=0.对xi-1决策后，已经确定了（x1，······xi-1），在决策 Xi 时问题处于下列两种状态之一：
①背包容量不足以装入物品i 则xi=0，背包不增加价值；
②背包容量可以装入物品i ，则xi=1，背包的价值就增加了vi 。
这两种情况下背包价值的最大者应该是对xi 决策后的背包价值。令V （i ，j ）表 示在前i(1
V(i,0)=V(0,j)=0
j
j>=Wi :V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi}
二、代码和运行结果截图
1、代码
#include
#include
#define n 5 //5种物品的一个背包
#define C 10 //背包容量
struct KnapSack
{
int w[C]; //n个物品的重量存储在数组w[]中
int v[n]; //n个物品的价值存储在数组v[]中
}knapsack;
int max(int a,int b) //求最大值
{
if(a>=b)
return a;
else
return b;
}
void main()
{
int V[n+1][C+1];
int i,j;
int si;
int vi;
int X; //X=0或X=1 判断物品是否装入
cout
for(i=1;i
{
cin>>knapsack.w[i]; //第i 个物品的重量 cin>>knapsack.v[i]; //第i 个物品的价值 }
cout
cout
cout
for(i=1;i
{
cout
|
cout
}
for(i=0;i
{
V[i][0]=0;
}
for(j=0;j
{
V[0][j]=0;
}
for(i=1;i
V[i][0]=0;
si=knapsack.w[i];
vi=knapsack.v[i];
for(j=1;j
{
V[i][j]=V[i-1][j];
if(si
{
V[i][j]=max(V[i][j],V[i-1][j-si]+vi);
}
}
}
cout
cout
for(i=0;i
{
cout
for(j=0;j
cout
cout
for(i=0;i
{
if(V[i][C]
X=1; //装入
else
X=0; //不装入
cout
}
2、运行结果截图
三、实验结果分析
动态规划算法是将待求解的问题分解成若干个子问题，但各子问题中往往是不相互独立的。动态规划算法将每个子问题只求解一次并将其保存在一个表格中，当在此求解此问
题时，只是简单的通过查表获得该子问题的解，从而避免了大量的重复计算。通过用动态算法思想对0/1背包问题算法的设计、调试我对动态规划的思想有了初步的了解和简单的应用。
一、实验内容
1、实验题目
0/1背包问题：给定n 中物品和一个背包，物品i 的重量是wi ，价值是vi ，背包的容量为c 。
2、实验目的
（1）深刻理解并掌握动态规划算法的设计思想；
（2）利用动态规划方法设计背包问题算法，掌握动态规划法
的基本思想和算法设计的基本步骤。
3、实验要求
设计0/1背包问题的动态规划算法，要求输出背包内物品
的最大价值以及选入背包的物品种类。利用c++语言实现
算法，给出程序的正确运行结果。
4、算法设计思想
0/1背包为题可以看作是决策一个序列（x1，x2······xn ），对任何一个变量xi 的 决策是决定xi=1还是xi=0.对xi-1决策后，已经确定了（x1，······xi-1），在决策 Xi 时问题处于下列两种状态之一：
①背包容量不足以装入物品i 则xi=0，背包不增加价值；
②背包容量可以装入物品i ，则xi=1，背包的价值就增加了vi 。
这两种情况下背包价值的最大者应该是对xi 决策后的背包价值。令V （i ，j ）表 示在前i(1
V(i,0)=V(0,j)=0
j
j>=Wi :V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi}
二、代码和运行结果截图
1、代码
#include
#include
#define n 5 //5种物品的一个背包
#define C 10 //背包容量
struct KnapSack
{
int w[C]; //n个物品的重量存储在数组w[]中
int v[n]; //n个物品的价值存储在数组v[]中
}knapsack;
int max(int a,int b) //求最大值
{
if(a>=b)
return a;
else
return b;
}
void main()
{
int V[n+1][C+1];
int i,j;
int si;
int vi;
int X; //X=0或X=1 判断物品是否装入
cout
for(i=1;i
{
cin>>knapsack.w[i]; //第i 个物品的重量 cin>>knapsack.v[i]; //第i 个物品的价值 }
cout
cout
cout
for(i=1;i
{
cout
|
cout
}
for(i=0;i
{
V[i][0]=0;
}
for(j=0;j
{
V[0][j]=0;
}
for(i=1;i
V[i][0]=0;
si=knapsack.w[i];
vi=knapsack.v[i];
for(j=1;j
{
V[i][j]=V[i-1][j];
if(si
{
V[i][j]=max(V[i][j],V[i-1][j-si]+vi);
}
}
}
cout
cout
for(i=0;i
{
cout
for(j=0;j
cout
cout
for(i=0;i
{
if(V[i][C]
X=1; //装入
else
X=0; //不装入
cout
}
2、运行结果截图
三、实验结果分析
动态规划算法是将待求解的问题分解成若干个子问题，但各子问题中往往是不相互独立的。动态规划算法将每个子问题只求解一次并将其保存在一个表格中，当在此求解此问
题时，只是简单的通过查表获得该子问题的解，从而避免了大量的重复计算。通过用动态算法思想对0/1背包问题算法的设计、调试我对动态规划的思想有了初步的了解和简单的应用。