KnapsackProblem/김태진

0/1 KnapSack problem

• Extremely simple, but hard to understand
• Using DP
• Can load same items several time

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

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;
}