0-1背包问题与完全背包问题C++实现动态规划

0-1背包动态规划解决问题

一、问题描述：

有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

二、总体思路：

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。

三、动态规划的原理及过程：

number＝4，capacity＝7

i 1 2 3 4

w(重量) 3 5 2 1

v(价值) 9 10 7 4

原理：

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

过程：

a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积（重量）；

b) 建立模型，即求max(V1X1+V2X2+…+VnXn)；

c) 约束条件，W1X1+W2X2+…+WnXn

d) 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；

e) 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：

假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解， 假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；

1 / 2

实验二、0-1背包问题（动态规划）

实验代码：

#include

int m[20][20];

int min(int w, int c)

{

int temp;

if (w < c) temp = w;

else

temp = c;

return temp;

}

int max(int w, int c)

{

int temp;

if (w > c) temp = w;

else

temp = c;

return temp;

}

void knapsack(int v[], int w[], int c, int n)

{

int jmax = min(w[n]-1, c);

for (int j = 0; j <= jmax; j++)

m[n][j] = 0;

for (int k= w[n]; k<= c; k++)

m[n][k] = v[n];

for(int i = n-1; i > 1; i--)

{

jmax = min(w[i]-1, c);

for(int j = 0; j <= jmax; j++)

m[i][j] = m[i+1][j];

for(int k = w[i]; k <= c; k++)

m[i][k] = max(m[i+1][k], m[i+1][k-w[i]]+v[i]);

}

m[1][c] = m[2][c];

if(c >= w[1])

m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);

}

void traceback(int x[], int w[], int c, int n)

XXXX大 学 计 算 机 学 院 实 验 报 告

计算机学院 2017 级 软件工程 专业 5 班 指导教师

学号 姓名 2019年 10 月 21 日 成绩

课程名称 算法分析与设计 实验名称 动态规划---0-1背包问题

实验目的 ①理解递归算法的概念

②通过模仿0-1背包问题，了解算法的思想

③练习0-1背包问题算法

实验仪器

和器材 电脑、jdk、eclipse

实

验

内

容

、

上

机

调

试

程

序

、

程

序

运

行

结

果

实验：0-1背包算法：给定N种物品，每种物品都有对应的重量weight和价值value，一个容量为maxWeight的背包，问：应该如何选择装入背包的物品，使得装入背包的物品的总价值最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也不能把同一个物品装入多次）代码如下所示：

public class KnapsackProblem {

/**

* @param weight 物品重量

* @param value 物品价值

* @param maxweight 背包最大重量

* @return maxvalue[i][j]中，i表示的是前i个物品数量，j表示的是重量

*/

public static int knapsack(int [] weight,int [] value,int maxweight){

实

验

内

容

、

上

机

调

试

程

序

、

程

序

运

行

结

果

int n = ;包问题的算法思想： 将前i个物品放入容量为w的背包中的最大价值。有如下两种情况：

①若当前物品的重量小于当前可放入的重量，便可考虑是否要将本件物品放入背包中或者将背包中的某些物品拿出来再将当前物品放进去；放进去前需要比较（不放这个物品的价值）和（这个物品的价值放进去加上当前能放的总重量减去当前物品重量时取i-1个物品是的对应重量时候的最高价值），如果超过之前的价值，可以直接放进去，反之不放。

动态规划之-0-1背包问题及改进

有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。在选择装入背包的物品时，对于每种物品i，只能选择装包或不装包，不能装入多次，也不能部分装入，因此成为0-1背包问题。

形式化描述为：给定n个物品，背包容量C >0,重量 第i件物品的重量w[i]>0, 价值v[i] >0 , 1≤i≤n.要求找一n元向量(X1,X2,…,Xn,), Xi∈{0,1}, 使得 ∑（w[i] * Xi） ≤C,且∑ v[i] * Xi达最大.即一个特殊的整数规划问题。

数学描述为：

求解最优值：

设最优值m(i,j)为背包容量为j、可选择物品为i，i+1，……，n时的最优值(装入包的最大价值)。所以原问题的解为m(1，C)

将原问题分解为其子结构来求解。要求原问题的解m(1，C)，可从m(n，C)，m(n-1，C)，m(n-2，C).....来依次求解，即可装包物品分别为（物品n）、（物品n-1，n）、（物品n-2，n-1，n）、……、（物品1，物品2，……物品n-1，物品n）。最后求出的值即为最优值m(1，C)。

若求m(i,j)，此时已经求出m(i+1,j)，即第i+1个物品放入和不放入时这二者的最大值。

对于此时背包剩余容量 j=0,1,2,3……C，分两种情况：

(1)当 w[i] > j ，即第i个物品重量大于背包容量j时，m(i,j)=m(i+1,j)

(2)当 w[i] <= j ，即第i个物品重量不大于背包容量j时，这时要判断物品i放入和不放入对m的影响。

若不放入物品i，则此时m(i,j)=m(i+1,j)

若放入物品i，此时背包

剩余容量为 j-w[i]，在子结构中已求出当容量k=0,1,2……C 时的最优值m(i+1,k)。所以此时m(i,j)=m(i+1,j-w[i])+v[i]。