0，1背包问题
Goods
capacity
weight
A
2
3
B
1
2
C
3
4
D
2
2
题目：有N件物品和一个容量为V的背包。第i件物品的重量是weight[i]，价值是value[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
最笨的办法：暴力枚举。
就是把所有的办法都列举一边，然后比较所有办法里面的价值总和，比较出价值总和最大的。
缺点：
费时间和空间导致效率很低
新学习的
代码如下：
#include <stdio.h> #include <string.h> int max(int a,int b){ if(a>b){ return a; } else{ return b; } } int main(){ int goods,i,j,rad[100][100],value[100],weight[100],capacity; memset(rad,0,sizeof(rad)); printf("please imput the number of goods: \n"); scanf("%d",&goods); printf("please imput the value and weight of each goods:\n"); for(i=1;i<=goods;i++){ scanf("%d%d",&weight[i],&value[i]); } scanf("%d",&capacity); for(i=1;i<=goods;i++){ for(j=0;j<=capacity;j++){ if(j==0){ rad[i][j]=0; } else if(j<weight[i]){ continue; } else{ rad[i][j]=max(rad[i-1][j-weight[i]]+value[i],rad[i-1][j]); } } } for(i=1;i<=goods;i++){ for(j=0;j<=capacity;j++){ printf("%d ",rad[i][j]); } printf("\n"); } printf("%d\n",rad[goods][capacity]); return 0; }