相信大家和我一样，在刚开始写背包问题时因为不会动态规划而无从下手，其实简单背包问题真的很简单，只要你仔细阅读这篇文章，就会很快解决~
题目
给定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数组存放重量和价值，输入背包容量等信息
#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]); }
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背包问题的解决方法，如果大家有更简单更优的解法，欢迎大家在评论区讨论哦~
写博客不易，希望大家多多关注和点赞，我会一直更新我的博客和大家一起进步的！
