一看就会的01简单背包问题

ゝ一纸荒年。 2024-03-30 09:26 52阅读 0赞

相信大家和我一样，在刚开始写背包问题时因为不会动态规划而无从下手，其实简单背包问题真的很简单，只要你仔细阅读这篇文章，就会很快解决~

题目

> 给定n种物品和一背包。物品i的重量（体积）是w~i，其价值为v~i，背包的容量为C。问：应如何选择装入背包的物品，使得装入背包中物品的总价值最大。
> 
> 要求：
> 
> \* 系统给出的第一个数字是背包容量，第二个数字是物品件数，然后分别给出每件物品的重量，再分别给出每件物品的价值。  
> \* 请依次输出装入背包的物品序号，总重量，总价值。

## 1.贪心算法 ##

首先我们想到的是**贪心算法**，**用单位重量的价值的大小来判定此物体是否要放入包中**，但是贪心算法**不一定是最优解**，为什么呢？

> 比如一个背包的最大容量是100
> 
> 编号 1 2 3 4
> 
> 一些物体的重量是50 10 60 40
> 
> 他们的重量分别是50 2 30 40
> 
> 显而易见单位重量价值排序为1>4>3>2
> 
> 在贪心算法下，我们在取完1和4以后，在取3时发现超过容量，就不继续往后取u，但是实际上我们的2号物品重量刚好不超，并且还增加了总价值，这就是贪心算法的缺陷所在，他的解并非是最优解

--------------------

那么贪心算法无法解决，我们就来暴力枚举，**枚举法（穷举法）**得出来的一定是**最优解**哦~

## 2.枚举法 ##

> \*\*算法描述（伪代码）:\*\*
> 
> for (i=0 to 2^n-1)
> 
> \{  
> 将 i 对应的二进制数按位存放到数组Y中；  
> 尝试按照装包方案y进行装包，则背包中物品的重量为CurWeight, 价值为CurValue；  
> 如果CurWeight>C，则丢弃该方案，继续尝试下一种方案；否则，若该方案优于以前的方案，即如果CurValue>Value，则暂存该方案：即X=Y，Value=CurValue， Weight= CurWeight。 继续循环；  
> \}

看了上述代码，可能你还会有些迷惑，简单的说，就是利用0与1的性质，取对应着乘以1，不取就对应着乘以0

#### 1.定义W和V数组存放重量和价值，输入背包容量等信息 ####

#### 2.通过枚举取与不取的可能有n的2^n次方种可能，（根据排列组合，n个物体取或不取有2^n种可能性），物品的取与不取正好对应着将0和1分别排列组合的放入一个数组里面。 ####

for (i = 1; i < pow(2, n); i++)
    	{
    		m = n-1;
    		//枚举取与不取，方法就是让对应的价值和重量乘以1或0，此时将0与1放在和价值和重量对应顺序的位置，方便相乘
    		for (j = 0; j < n; j++)
    		{
    			arr[m--] = (1&(i>>j)); 
    		}

> **这里的（1&（i>>j))指的是将i右移j位2进制位以后与1的二进制位取并**

#### **3.将每一种1到2^n种可能性比较大小，先判断是否超过容量，在判断是否是最大价值，在每一次放入背包时一定要记**得清空背包以便于下一次计算**哦~** ####

清空背包以便于下一次计算
    		W = 0;
    		V = 0;
    		//将东西放入背包
    		for (k = 0; k < n; k++)
    		{
    			W += arr[k] * w[k];
    			V += arr[k] * v[k];
                背包现在的重量和价值
    		}
    		//比较是否超过容量
    		if (W <= c)
    		{
    			//比较是否是最大价值
    			if (V > MaxV)
    			{
    				MaxV = V;
    				MaxW = W;
    				count = 0;
    				for (int h = 0; h < n; h++)
    				{
    					//应题目要求将序号存起来方便打印
    					if (arr[h] == 1)
    					{
    						x[count++] = h+1;
    					}
    				}
    			}
    		}
    	}

#### 4.打印出结果即可 ####

for (i = 0; i < count; i++)
    	{
    		printf("%d ", x[i]);
    	}
    	printf("%d %d", MaxW, MaxV);
    }

## 完整代码 ##

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<math.h>
    int main()
    {
    	int c,k,n,i,j,m,V,W,MaxV=0,MaxW=0,count;
    	scanf("%d %d", &c, &n);
    	int w[1000] = { 0 };
    	int v[1000] = { 0 };
    	int arr[1000] = { 0 }, x[1000] = { 0 };
    	for (i = 0; i < n; i++)
    	{
    		scanf("%d", &w[i]);
    	}
    	for (i = 0; i < n; i++)
    	{
    		scanf("%d", &v[i]);
    	}
    	for (i = 1; i < pow(2, n) - 1; i++)
    	{
    		m = n-1;
    		for (j = 0; j < n; j++)
    		{
    			arr[m--] = (1&(i>>j)); 
    		}
    		W = 0;
    		V = 0;
    		for (k = 0; k < n; k++)
    		{
    			W += arr[k] * w[k];
    			V += arr[k] * v[k];
    		}
    		if (W <= c)
    		{
    			if (V > MaxV)
    			{
    				MaxV = V;
    				MaxW = W;
    				count = 0;
    				for (int h = 0; h < n; h++)
    				{
    					if (arr[h] == 1)
    					{
    						x[count++] = h+1;
    					}
    				}
    			}
    		}
    	}
    	for (i = 0; i < count; i++)
    	{
    		printf("%d ", x[i]);
    	}
    	printf("%d %d", MaxW, MaxV);
    }

以上就是简单01背包问题的解决方法，如果大家有更简单更优的解法，欢迎大家在评论区讨论哦~

写博客不易，希望大家多多关注和点赞，我会一直更新我的博客和大家一起进步的！