= 0/1 KnapSack problem = * Extremely simple, but hard to understand * Using DP {{{ #include #include #include using namespace std; int f[10001][10001] = {0}; int main() { int i,Wei,Num,k,w,Max=0; int weight[10001] ={0}; int price[10001] ={0}; scanf("%d %d",&Wei,&Num); for(i=1;i<=Num;i++){ scanf("%d %d",&price[i], &weight[i]); } for(k = 1; k <= Num; k++){ for(w = 1; w <= Wei; w++){ if(w >= weight[k]){ f[k][w] = max(f[k-1][w], f[k][w - weight[k]] + price[k]); }else{ f[k][w] = f[k-1][w]; } } } printf("%d",f[k-1][w-1]); return 0; } }}}