在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
注意:在本题中,所有的体积值均为整数。01的意思是,每个物品都是一个整体,要么整个都要,要么都不要。
1)最优子结构
考虑所有物品的子集合,考虑第n个物品都有两种情况: 1. 包括在最优方案中 2. 不在最优方案中
因此,能获得的最大价值,即为以下两个值中较大的那个
1) 在剩下 n-1 个物品中(剩余 W 重量可用)的情况能得到的最大价值 (即排除了 第n个物品)
2) 第n个物品的价值 加上 剩下 剩下的 n-1 个物品(剩余W- wn的重量)能得到的最大价值。(即包含了第n个物品)
如果第n个物品的重量,超过了当前的剩余重量W,那么只能选情况1), 排除第n个物品。
2) 重叠子问题
下面是一个递归的实现,按照上面的最优子结构。
01 |
/* 朴素的递归实现 0-1 背包 */ |
02 |
#include<stdio.h> |
03 |
04 |
int max( int a, int b) { return (a > b)? a : b; }
|
05 |
06 |
// 返回 前n个物品在容量为W时,能得到的最大价值 |
07 |
int knapSack( int W, int wt[], int val[], int n)
|
08 |
{ |
09 |
// 没有物品了
|
10 |
if (n == 0 || W == 0)
|
11 |
return 0;
|
12 |
13 |
// 如果当前第n个物品超重了,就排除在外
|
14 |
if (wt[n-1] > W)
|
15 |
return knapSack(W, wt, val, n-1);
|
16 |
17 |
//返回两种情况下最大的那个 (1) 包括第n个物品 (2) 不包括第n个物品
|
18 |
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
|
19 |
knapSack(W, wt, val, n-1)
|
20 |
);
|
21 |
} |
22 |
23 |
// 测试 |
24 |
int main()
|
25 |
{ |
26 |
int val[] = {60, 100, 120};
|
27 |
int wt[] = {10, 20, 30};
|
28 |
int W = 50;
|
29 |
int n = sizeof (val)/ sizeof (val[0]);
|
30 |
printf ( "%d" , knapSack(W, wt, val, n));
|
31 |
return 0;
|
32 |
} |
这种方法其实就是搜索了所有的情况,但是有很多重复的计算。时间复杂度是指数级的 O(2^n)。
01 |
在下面的递归树中 K() 代表 knapSack(). |
02 |
输入数据如下: |
03 |
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30} |
04 |
05 |
K(3, 2) ---------> K(n, W)
|
06 |
/ \
|
07 |
/ \
|
08 |
K(2,2) K(2,1)
|
09 |
/ \ / \
|
10 |
/ \ / \
|
11 |
K(1,2) K(1,1) K(1,1) K(1,0)
|
12 |
/ \ / \ / \
|
13 |
/ \ / \ / \
|
14 |
K(0,2) K(0,1) K(0,1) K(0,0) K(0,1) K(0,0) |
可见相同的子问题被计算多次。01背包满足动态规划算法的两个基本属性(重叠子问题和最优子结构)。可以通过自下而上的打表,存储中间结果,来避免重复计算。动态规划解法如下:
01 |
#include<stdio.h> |
02 |
int max( int a, int b) { return (a > b)? a : b; }
|
03 |
04 |
int knapSack( int W, int wt[], int val[], int n)
|
05 |
{ |
06 |
int i, w;
|
07 |
int dp[n+1][W+1];
|
08 |
09 |
for (i = 0; i <= n; i++)
|
10 |
{
|
11 |
for (w = 0; w <= W; w++)
|
12 |
{
|
13 |
if (i==0 || w==0)
|
14 |
dp[i][w] = 0;
|
15 |
else if (wt[i-1] <= w)
|
16 |
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
|
17 |
else
|
18 |
dp[i][w] = dp[i-1][w];
|
19 |
}
|
20 |
}
|
21 |
return dp[n][W];
|
22 |
} |
23 |
24 |
int main()
|
25 |
{ |
26 |
int val[] = {60, 100, 120};
|
27 |
int wt[] = {10, 20, 30};
|
28 |
int W = 50;
|
29 |
int n = sizeof (val)/ sizeof (val[0]);
|
30 |
printf ( "%d" , knapSack(W, wt, val, n));
|
31 |
return 0;
|
32 |
} |
空间复杂度和时间复杂度都为 O(Wn). 由于打表的过程中,计算的当前行只依赖上一行,空间复杂度可以优化为O(W);
参考:http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/
更多关于算法分析的文章:http://www.acmerblog.com/category/zhuanti/algorithm
相关推荐
C#实现-动态规划-01背包问题(Knapsack),代码根据软考书籍中C代码的内容改写,已调试使用无误。
01背包问题,桂林电子科技大学算法设计实验报告
利用动态规划方法求解经典0-1背包问题,仅供参考,欢迎指正
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
提供0-1背包问题c++代码,实现功能如下: /**输入参数: * @param m 表示背包的最大容量 * @param n 表示商品个数 * @param a[] 每个商品的容量 * @param p[] 每个商品的价值 */ /**输出: 求最大商品value*/
本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。
python动态规划背包问题算法-01背包问题(动态规划算法) 给定 N 种物品和⼀个容量为 V 的背包,物品 i 的体积是 wi,其价值为 ci 。 (每种物品只有⼀个) 问:如何选择装⼊背包的物品,使得装⼊背包中的物品的总...
利用动态规划算法实现了01背包问题,并取得了良好的效果。
算法-动态规划- 背包问题 P01- 0-1背包(包含源程序).rar
动态规划法解决0-1背包问题,非常实用,课程实验经常用到
01背包-动态规划-c语言 已调通
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
计算机算法设计 动态规划法解0-1背包问题 c++ c语言编写
用C++实现的0-1背包问题的动态规划解法程序。注释详实,可读性好。
动态规划解决01背包问题,算法简单,思路清晰,逻辑严整
使用动态规划求解01背包问题的程序,使用C语言编写。
解0-1背包问题的动态规划算法及其两次改进,许薇,周继鹏,给出了用动态规划算法解决0-1背包问题的证明,分析了动态规划算法解决0-1背包问题的不足和性能。然后,针对用该动态规划算法解决0-1
用c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15