
背包是一个袋子。而背包问题涉及根据物品的价值将物品放入袋子中。它的目标是最大化袋子内的价值。在0-1背包中,您可以选择放入物品或丢弃它,没有将物品的一部分放入背包的概念。
示例问题
Value of items = {20, 25,40}
Weights of items = {25, 20, 30}
Capacity of the bag = 50
权重分布
25,20{1,2}
20,30 {2,3}
If we use {1,3} the weight will be above the max allowed value.
For {1,2} : weight= 20+25=45 Value = 20+25 = 45
For {2,3}: weight=20+30=50 Value = 25+40=65
最大值为65,因此我们将物品2和3放入背包中。
0-1背包问题的程序
#include<stdio.h>
int max(int a, int b) {
if(a>b){
return a;
} else {
return b;
}
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int knap[n+1][W+1];
for (i = 0; i <h2>输出</h2>
<pre class="brush:php;toolbar:false;">The solution is : 65
13万字C语言保姆级教程(深入):立即使用
在学习笔记中,你将探索c语言的核心概念和高级技巧!











