题目：给定一个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,4
4,5
5,6
0 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
