动态规划0-1背包问题

动态规划0-1背包问题这篇博客讲的很不错 http://blog.csdn.net/yeepom/article/details/8712224

简单概述一下

问题：有n个物品，第i个物品价值为vi，重量为wi，其中vi和wi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。

关键是找到递推公式，递推公式中要包括所有的情形。

#include<windows.h>
#include<string.h> #include <stdio.h>
void DP(int n, int W, int c[][18], int *v, int *wei) { memset(*c, 0, (W + 1) * sizeof(int));//第0行置零初始化，物品个数0
    for (int i = 1; i <= n; i++) { c[i][0] = 0;//第0列，w=0，所有置零
        for (int w = 1; w <= W; w++) { if (wei[i - 1] > w)    //此处比较是关键
 { c[i][w] = c[i - 1][w]; } else { int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];    //注意wei和v数组中的第i个应该为wei[i-1]和v[i-1]
                if (c[i - 1][w] > temp) { c[i][w] = c[i - 1][w]; } else c[i][w] = temp; } } } } void findPath(int c[][18], int *x, int *wei, int n, int W) { int w = W; for (int i = n; i >= 1; i--)//从高编号物品开始看
 { if (c[i][w] == c[i - 1][w])//说明i物品对价值增高不起作用，不能或者不必放
 { x[i - 1] = 0; } else    //起作用，然后将其排除考虑i-1物品
 { x[i - 1] = 1; w = w - wei[i - 1]; } } } int main() { int n = 5;    //物品数量最大值 >=0
    int W = 17;    //容量最大值 >=0
    int w[] = { 3, 4, 7, 8, 9 };//重量数组int w[]={-1,3, 4, 7, 8, 9 }
    int v[] = { 4, 5, 10, 11, 13 };//价值数组
    int c[6][18] = { 0 };    //所有规模的价值数组
 DP(n, W, c, v, w); printf("%d\n", c[5][17]); int x[5];//物品是否放进背包情况表，0不放，1放入
 findPath(c, x, w, n, W); for (int i = 0; i < n; i++) printf("%d \n", x[i]); system("pause"); return 0; }

 

这种方法有一定的好处，能够消除递归，还能直观的得出findpath()的结果

递归实现DP

int dp(int n, int W, int *v, int *wei) { if (n == 0 || W == 0) return 0; else if (wei[n - 1] > W) return dp(n - 1, W, v, wei); else { int valueA = dp(n - 1, W - wei[n - 1], v, wei) + v[n - 1]; int valueB = dp(n - 1, W, v, wei); return valueA > valueB ? valueA : valueB; } }