必威体育Betway必威体育官网
当前位置:首页 > IT技术

0/1背包问题

时间:2019-08-15 14:42:07来源:IT技术作者:seo实验室小编阅读:81次「手机版」
 

背包问题

0/1背包问题

文章目录

    • 0/1背包问题
      • 【问题描述】
      • 【问题分析】
      • 算法设计
      • 【算法分析】

【问题描述】

给定nnn种物品和一个背包,物品iii(1in1 \leq i \leq n1≤i≤n)的重量是ωi\omega_iωi​,其价值是viv_ivi​,背包的容量为CCC,对于每种物品只有两种选择,即装入背包或不装入背包。问题是如何选择装入背包的物品使得装入背包的物品的总价值最大?

【问题分析】

递推方程

V(i,j)={V(i1,j)j&lt;ωimax{V(i1,j),V(i1,jωi)+vi}jωi V(i, j) = \begin{cases} V(i-1, j) &amp; j &lt; \omega_i \\ max\{ V(i-1, j), V(i-1, j-\omega_i)+v_i \} &amp; j\geq \omega_i \end{cases} V(i,j)={V(i−1,j)max{V(i−1,j),V(i−1,j−ωi​)+vi​}​j<ωi​j≥ωi​​

解释说明

  1. 背包不足以装入物品iii,则装入前iii个物品所得到的最大价值和装入前i1i-1i−1个物品得到的最大价值相等,即xi=0x_i = 0xi​=0,背包不增加任何价值。
  2. 背包容量可以装入物品iii,此时可能存在两种情况,即考虑不装
    • 若把第iii个物品没有被装入背包,则与第一种情况相同
    • 若把第iii个物品装入背包,则背包中物品的总价值等于把前i1i-1i−1个物品装入容量为jωij - \omega_ij−ωi​的背包中得到的最大价值加上第iii个物品装入背包的价值viv_ivi​

【算法设计】

nnn个物品的重量存储在数组w[n]中,价值存储在数组v[n]中,背包的容量为C,数组V[n+1][C+1]存放迭代结果,其中V[i][j]表示前iii个物品装入容量为jjj的背包所能获得的最大价值,数组x[n]存储装入背包的物品。

初始化的条件为将前面的iii个物品装入容量为0的背包中(对应着二维数组V中的第一列)和将0个物品装入容量为jjj的背包(对应着二维数组V中的第一行)

对应的C++代码如下:

/*
 * 0/1背包问题
 * 3/15/2019
 */

#include <iOStream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

/*
 * w:重量数组
 * v:价值数组
 * n:物品数
 * C:背包容量
 */
int KnapSack(int *w, int *v,int n, int C)
{
	// V:迭代计算的结果
	int **V = new int*[n+1];
	for(int i=0; i<=n; i++)
		V[i] = new int[C+1];

	//初始化
	for(int j=0; j<=C; j++)
	{
		V[0][j] = 0;
	}
	for(int i=0; i<=n; i++)
	{
		V[i][0] = 0;
	}
//	for(int i=0; i<=n; i++)
//	{
//		for(int j=0; j<=C; j++)
//			cout << V[i][j] << " ";
//		cout << endl;
//	}

	for(int i=1; i<=n; i++)	//遍历物品
	{
		for(int j=1; j<=C; j++) 	//遍历容量,注意j代表的就是当前背包的容量
		{
			if(w[i] > j)	//装不进对应于第一种情况
			{
				V[i][j] = V[i-1][j];
			}
			else //容量决定理论上可以装进,对应于第二种情况
			{
				V[i][j] = max(V[i-1][j], V[i-1][j-w[i]]+v[i]);
			}
		}
	}

	//打印代价矩阵的信息
	for(int i=0; i<=n; i++)
	{
		for(int j=0; j<=C; j++)
			cout << setw(3) << V[i][j] << " ";
		cout << endl;
	}

	//检测选中的节点
	int *x = new int[n+1];	//表示选中与否
	for(int i=n, j = C; i>0; i--)
	{
		if(V[i][j] > V[i-1][j])	//装入该物品
		{
			x[i] = 1;	//被选中了
			j -= w[i];	//更新背包的剩余容量
		}
		else
		{
			x[i] = 0;	//表示没有被选中
		}
	}
	for(int i=1; i<=n; i++)
	{
		if(x[i] == 1)
		{
			cout << "物品" << i << "被选中, " << "重量: " << w[i] << "价值: " << v[i] << endl;
		}

	}

	return V[n][C];

}
int main()
{
	fstream is("input.txt");
	int n, C;
	is >> n >> C;
	int *w = new int[n+1];
	int *v = new int[n+1];
	for(int i=1; i<=n; i++)
	{
		is >> w[i];
	}
	for(int i=1; i<=n; i++)
	{
		is >> v[i];
	}

//	for(int i=0; i<=n; i++)
//		cout << w[i] << " " << v[i] << endl;
//	cout << C << endl;

	cout << "最大价值: " << KnapSack(w, v, n, C) << endl;
	return 0;
}
input.txt

5 
10
2 2 6 5 4
6 3 5 4 6

程序运行结果如下:

【算法分析】

程序过程推导

求解第一个阶段(i = 1)的子问题即装入前一个物品确定各种情况下背包能够获得的最大价值

j=1&lt;2=ω2j = 1 &lt; 2 = \omega_2j=1<2=ω2​无法装入,对应于情况1 V[1][1] = V[0][1] = 0

j=2=ω2j = 2 = \omega_2j=2=ω2​可以装入,对应于情况2,此时max{V[0][2] = 0, V[0][0] + 6} = 6

j=3&gt;ω2j = 3 &gt; \omega_2j=3>ω2​可以装入,对应于情况2,此时max{V[0][3] = 0, V[0][1] + 6} = 6

同理可得剩余的V[1][j] = 6

求解第二个阶段(i = 2)的子问题即装入前两个物品

容量j=1&lt;2=ω2j = 1 &lt; 2 = \omega_2j=1<2=ω2​无法装入,对应于情况1此时V[2][1] = V[1][1] = 0

容量j=2=2=ω2j = 2 = 2 = \omega_2j=2=2=ω2​可以装入,对应于情况2此时max{V[1][2] = 6, V[1][0] + 3 = 3} = 6

容量j=3&gt;2=ω2j = 3 &gt; 2 = \omega_2j=3>2=ω2​可以装入,对应于情况2此时max{V[1][3] = 6, V[1][1] + 3 = 3} = 6

容量j=4&gt;2=ω2j = 4 &gt; 2 = \omega_2j=4>2=ω2​可以装入,对应于情况2此时max{V[1][4] = 6, V[1][2] + 3 = 9} = 9

同理可得剩余的V[2][j] = 9

求解第三个阶段(i = 3)的子问题即装入前三个物品

容量j=1&lt;6=ω3j = 1 &lt; 6 = \omega_3j=1<6=ω3​ 无法装入,对应于情况1,此时V[3][1] = V[2][1] = 0

容量j=2&lt;6=ω3j = 2 &lt; 6 = \omega_3j=2<6=ω3​ 无法装入,对应于情况1,此时V[3][2] = V[2][2] = 6

容量j=3&lt;6=ω3j = 3 &lt; 6 = \omega_3j=3<6=ω3​ 无法装入,对应于情况1,此时V[3][3] = V[2][3] = 6

容量j=4&lt;6=ω3j = 4 &lt; 6 = \omega_3j=4<6=ω3​ 无法装入,对应于情况1,此时V[3][4] = V[2][4] = 9

容量j=5&lt;6=ω3j = 5 &lt; 6 = \omega_3j=5<6=ω3​ 无法装入,对应于情况1,此时V[3][5] = V[2][5] = 9

容量j=6=6=ω3j = 6 = 6 = \omega_3j=6=6=ω3​可以装入,对应于情况2此时max{V[2][6] = 9, V[2][0] + 5 = 5} = 9

容量j=7&gt;6=ω3j = 7 &gt; 6 = \omega_3j=7>6=ω3​可以装入,对应于情况2此时max{V[2][7] = 9, V[2][1] + 5 = 5} = 9

容量j=8&gt;6=ω3j = 8 &gt; 6 = \omega_3j=8>6=ω3​可以装入,对应于情况2此时max{V[2][8] = 9, V[2][2] + 5 = 11} = 11

容量$j = 9 > 6 = \omega_3 KaTeX parse ERROR: expected '}', got '\[' at position 19: …入,对应于情况2此时max{V\̲[̲2][9] = 9, V\[2…j = 10 > 6 = \omega_3$可以装入,对应于情况2此时max{V[2][10] = 9, V[2][4] + 5 = 14} = 14

求解第四个阶段(i = 4)的子问题即装入前四个物品

容量j=1&lt;5=ω4j = 1 &lt; 5 = \omega_4j=1<5=ω4​无法装入,对应于情况1,此时V[4][1] = V[3][1] = 0

容量j=2&lt;5=ω4j = 2 &lt; 5 = \omega_4j=2<5=ω4​无法装入,对应于情况1,此时V[4][2] = V[3][2] = 6

容量j=3&lt;5=ω4j = 3 &lt; 5 = \omega_4j=3<5=ω4​无法装入,对应于情况1,此时V[4][3] = V[3][3] = 6

容量j=4&lt;5=ω4j = 4 &lt; 5 = \omega_4j=4<5=ω4​可以装入,对应于情况1,此时V[4][4] = V[3][4] = 9

容量j=5=5=ω4j = 5 = 5 = \omega_4j=5=5=ω4​可以装入,对应于情况2,此时max{V[3][5] = 9, V[3][0] + 4 = 0 + 4} = 9

容量j=6&gt;5=ω4j = 6 &gt; 5 = \omega_4j=6>5=ω4​可以装入,对应于情况2,此时max{V[3][6] = 9, V[3][1] + 4 = 0 + 4} = 9

容量j=7=5=ω4j = 7 = 5 = \omega_4j=7=5=ω4​可以装入,对应于情况2,此时max{V[3][7] = 9, V[3][2] + 4 = 6 + 4} = 10

容量j=8=5=ω4j = 8 = 5 = \omega_4j=8=5=ω4​可以装入,对应于情况2,此时max{V[3][8] = 11, V[3][3] + 4 = 6 + 4} = 11

容量j=9=5=ω4j = 9 = 5 = \omega_4j=9=5=ω4​可以装入,对应于情况2,此时max{V[3][9] = 11, V[3][4] + 4 = 9 + 4} = 13

容量j=10=5=ω4j = 10 = 5 = \omega_4j=10=5=ω4​可以装入,对应于情况2,此时max{V[3][10] = 14, V[3][5] + 4 = 9 + 4} = 14

求解第五个阶段(i = 5)的子问题即装入前五个物品

容量j=1&lt;4=ω5j = 1 &lt; 4 = \omega_5j=1<4=ω5​无法装入,对应于情况1,此时V[5][1] = V[4][1] = 0

容量j=2&lt;4=ω5j = 2 &lt; 4 = \omega_5j=2<4=ω5​无法装入,对应于情况1,此时V[5][2] = V[4][2] = 6

容量j=3&lt;4=ω5j = 3 &lt; 4 = \omega_5j=3<4=ω5​无法装入,对应于情况1,此时V[5][3] = V[4][3] = 6

容量j=4=4=ω5j = 4 = 4 = \omega_5j=4=4=ω5​可以装入,对应于情况2,此时max{V[4][4] = 9, V[4][0] + 6 = 6} = 9

容量j=5&gt;4=ω5j = 5 &gt; 4 = \omega_5j=5>4=ω5​可以装入,对应于情况2,此时max{V[4][5] = 9, V[4][1] + 6 = 6} = 9

容量j=6&gt;4=ω5j = 6 &gt; 4 = \omega_5j=6>4=ω5​可以装入,对应于情况2,此时max{V[4][6] = 9, V[4][2] + 6 = 12} = 12

容量j=7&gt;4=ω5j = 7 &gt; 4 = \omega_5j=7>4=ω5​可以装入,对应于情况2,此时max{V[4][7] = 10, V[4][3] + 6 = 12} = 12

容量j=8&gt;4=ω5j = 8 &gt; 4 = \omega_5j=8>4=ω5​可以装入,对应于情况2,此时max{V[4][8] = 11, V[4][4] + 6 = 15} = 15

容量j=9&gt;4=ω5j = 9 &gt; 4 = \omega_5j=9>4=ω5​可以装入,对应于情况2,此时max{V[4][9] = 13, V[4][5] + 6 = 15} = 15

容量j=10&gt;4=ω5j = 10 &gt; 4 = \omega_5j=10>4=ω5​可以装入,对应于情况2,此时max{V[4][10] = 14, V[4][6] + 6 = 15} = 15

结果与最后得出的一致。

一定要注意数组V的大小,需要开[n+1][C+1],因为物品是由一个零行和n个物品组成,容量是由一个零行和C容量组成。

一定要注意下标对应,是从0开始还是从1开始。

在算法KnapSackKnapSackKnapSack中,第一个forforfor循环的时间性能是O(C)O(C)O(C),第二个forforfor循环的时间性能是O(n)O(n)O(n),第三个循环是两层嵌套的forforfor循环,其时间性能是O(n×C)O(n \times C)O(n×C),第四个forforfor循环的时间性能是O(n)O(n)O(n),所以,算法的时间复杂性为O(n×C)O(n \times C)O(n×C)

Online 0/1 Knapsack problem solver

相关阅读

算法之0-1背包问题

一、问题描述:给定n种物品和一个背包,物品i的重量是wi,其价值是vi,背包的容量为c。问应该如何选择装入背包中的物品,使得装入背包中的

01背包问题,最良心的讲解了

1、动态规划(DP)动态规划(Dynamic Programming,DP)与分治区别在于划分的子问题是有重叠的,解过程中对于重叠的部分只要求解一次,记录下结

【动态规划】01背包问题(通俗易懂,超基础讲解)

问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面

【DP算法篇之初学】背包问题

昨天做了爱奇艺的内推笔试,编程题又出现了动态规划问题,感觉动态规划出现的概率好大,需要加强下。这里借用背包问题开始我们的学习。

彻底理解0-1背包问题

0-1背包问题 给定n个重量为w1w_1w1​,w2w_2w2​,w3w_3w3​,…,wnw_nwn​,价值为v1v_1v1​,v2v_2v2​,v3v_3v3​,…,vnv_nvn​的物品

分享到:

栏目导航

推荐阅读

热门阅读