问题:
我们有一个背包,背包总的承载重量是Wkg。现在我们有n个物品,每个物品的重量不等,并且不可分割,我们现在期望选择几件物品,装载到背包中。在不超过背包所能装载重量的前提下,如何让背包中的物品的总重量最大?
如果用回溯算法从头到尾搜索的话,复杂度为2^n,这里面有很多的重复子问题,所以考虑合并子问题,使用动态规划。
整个过程可以分为n个阶段,每个阶段会决策一个物品是否放入背包中。
代码:
1 #include <iostream> 2 #include <stack> 3 int main() 4 { 5 int threshold = 100; //最大承载100kg 6 int items[10] = {11, 4, 59, 68, 28, 70, 34, 7, 7, 98}; //一共有10个物品 7 int states[10][threshold + 1] = {0}; 8 9 if(items[0] <= threshold) //第一个物品放进背包 10 states[0][items[0]] = 1; 11 12 for(int i = 1; i < sizeof(items) / sizeof(int); i++) 13 { 14 for(int j = 0; j < threshold + 1; j++) // 第i个物品不放入背包 15 { 16 states[i][j] = states[i - 1][j]; 17 } 18 19 for(int j = 0; j < threshold + 1; j++) 20 { 21 if(j + items[i] <= threshold) 22 if(states[i - 1][j] == 1) 23 states[i][j + items[i]] = 1; 24 } 25 } 26 27 int max_eight = 0; 28 for(int i = threshold; i >= 0; i--) 29 { 30 if(states[9][i] == 1) 31 { 32 max_eight = i; 33 break; 34 } 35 } 36 37 std::stack<int> s; 38 int right = threshold; 39 for(int i = 10 - 1; i >= 0; i--) 40 { 41 for(int j = right; j >= 0; j--) 42 { 43 if(states[i][j] == 1) 44 { 45 if(i - 1 >= 0) 46 { 47 if(states[i-1][j-items[i]] == 1) 48 { 49 s.push(items[i]); 50 right = j - items[i]; 51 break; 52 } 53 else 54 break; 55 } 56 else 57 s.push(items[i]); 58 } 59 } 60 } 61 std::cout << "max_eight : " << max_eight << std::endl; 62 63 while(!s.empty()) 64 { 65 std::cout << s.top() << " "; 66 s.pop(); 67 } 68 std::cout << std::endl; 69 70 return 0; 71 }
运行结果:
0-1 背包问题升级:
上面的背包问题只涉及背包重量和物品重量。我们现在引入物品价值这一变量。对于一组不同重量、不同价值、不可分割的物品,我们选择将某些物品装入背包,在满足背包最大重量限制的前提下,背包中可装入物品的总价值是多少?
代码:
1 #include <iostream> 2 #include <stack> 3 int main() 4 { 5 int threshold = 100; //最大承载100kg 6 int items[10] = {11, 4, 59, 68, 28, 70, 34, 7, 7, 98}; //一共有10个物品 7 int values[10]= {20, 20, 40, 79, 33, 9, 25, 3, 5, 90}; //每个物品的价值 8 int states[10][threshold + 1] = {0}; 9 10 if(items[0] <= threshold) //第一个物品放进背包 11 states[0][items[0]] = values[0]; 12 13 for(int i = 1; i < sizeof(items) / sizeof(int); i++) 14 { 15 for(int j = 0; j < threshold + 1; j++) // 第i个物品不放入背包 16 { 17 states[i][j] = states[i - 1][j]; 18 } 19 20 for(int j = 0; j < threshold + 1; j++) 21 { 22 if(j + items[i] <= threshold) 23 if(states[i - 1][j] > 0) 24 { 25 int value = states[i-1][j] + values[i]; 26 if(value > states[i][j + items[i]]) 27 states[i][j + items[i]] = value; 28 } 29 } 30 } 31 32 int max_eight = 0; 33 int max_value = 0; 34 for(int i = threshold; i >= 0; i--) 35 { 36 if(states[9][i] > 0) 37 { 38 std::cout << "[" << i << "] : " << states[9][i] << ", "; 39 if(states[9][i] > max_value) 40 { 41 max_value = states[9][i]; 42 max_eight = i; 43 } 44 } 45 } 46 std::cout << std::endl; 47 48 49 std::cout << "max_eight : " << max_eight << std::endl; 50 std::cout << "max_value : " << max_value << std::endl; 51 52 53 return 0; 54 }
运行结果: