01背包问题 动态规划 c swift 双版本

题目：给定一个n种物品和 一个能装m重量的背包， 物品重量w，价值是p。问：如何才能使背包m重量 ，装最多价值的物品。

概念：为什么这种题目会 用动态规划，不用贪心算法？--我个人理解是，贪心算法每一步的最优解，可能导致最后的答案不是最优解。--而动态规划，可以在上一步或前几步不是最优解的情况下，解得当前这一步是最优解。/// 这位博主写的 非常好，思路异常清晰。http://www.cnblogs.com/xy-kidult/archive/2013/03/25/2970313.html#include <stdio.h>

                int c[10][10] = {0};                void knapsack(int m,int n)                {                    int i,j,w[10],p[10];                    for(i=1;i<n+1;i++)                        scanf("\n%d,%d",&w[i],&p[i]);///  这里保存 物品重量和价值                                                           for(i=1;i<n+1;i++)                        for(j=1;j<m+1;j++)                        {                            if (j<w[i]) {///背包小，装不下w[i] 物品                                                                c[i][j]= c[i-1][j];  /// 这里 赋值 装不下的值                                                            }else if(c[i-1][j-w[i]]+p[i]>c[i-1][j]){///这里是 c[i-1][j-w[i]]装下w[i] 和 c[i-1][j]不装w[i] 的价值大小                                                                c[i][j] = c[i-1][j-w[i]]+p[i];///这里赋值 把w[i] 装进去                                                            }else{///这里是，背包能装下w[i]物品，但是不装w[i]物品是最优解                                                                c[i][j] = c[i-1][j];///赋值不装w[i]，为最优                            }                        }                }                int main()                {                    int m,n;int i,j;                    printf("请输入背包总重量，物品总数量\n");                                        scanf("%d,%d",&m,&n);                                        printf("输入每个物品的重量和价值:\n");                                        knapsack(m,n);                                        printf("\n");                                        for(i=0;i<=n;i++)                        for(j=0;j<=m;j++)                        {                            printf("%d      ",c[i][j]);                            if(j>m-1)printf("\n");                        }                    printf("\n");                }

输入 数据请输入背包总重量，物品总数量10,3输入每个物品的重量和价值:3,44,55,60 0 0 0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4 4 4 4
0 0 0 4 5 5 5 9 9 9 9
0 0 0 4 5 6 6 9 10 11 11

最优解 价值11

swuft 版本 仅供娱乐import UIKit

                        var c =  [[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0]]                        ///保存价值与质量                        ///m为背包的承重，n有多少个物品                        func knap(m:Int,n:Int){                                                        var w = [0,3,4,5,0,0,0,0,0,0,0,0,0]                            var p = [0,4,5,6,0,0,0,0,0,0,0,0,0]                                                        for i in 1...n+1 {                                                                for j in 1...m+1{                                                                        if j < w[i]{//装不 下                                                                                c[i][j] = c[i-1][j]                                                                    }else if(c[i-1][j-w[i]]+p[i]) > c[i-1][j]{ /// 装的下 比较划算， 所以装进去                                                                                c[i][j] = c[i-1][j-w[i]]+p[i]                                                                            }else{/// 装的下 比较 不装比较划算                                                                                c[i][j] = c[i-1][j]                                    }                                                                    }                            }                                                    }                         knap(10, n:3)

个人博客： www.liangtongzhuo.com