KnapsackProblem/김태진 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:06Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 8:		Line 8:

	using namespace std;		using namespace std;
	int f[10001][10001] = {0};		int f[10001][10001] = {0};
	int main()		int main()
	{		{
	int i,Wei,Num,k,w,Max=0;		int i,Wei,Num,k,w,Max=0;
	int weight[10001] ={0};		int weight[10001] ={0};
	int price[10001] ={0};		int price[10001] ={0};
	scanf("%d %d",&Wei,&Num);		scanf("%d %d",&Wei,&Num);
	for(i=1;i<=Num;i++){		for(i=1;i<=Num;i++){
	scanf("%d %d",&price[i], &weight[i]);		scanf("%d %d",&price[i], &weight[i]);
	}		}

	for(k = 1; k <= Num; k++){		for(k = 1; k <= Num; k++){
	for(w = 1; w <= Wei; w++){		for(w = 1; w <= Wei; w++){
	if(w >= weight[k]){		if(w >= weight[k]){
	f[k][w] = max(f[k-1][w], f[k][w - weight[k]] + price[k]);		f[k][w] = max(f[k-1][w], f[k][w - weight[k]] + price[k]);
	}else{		}else{
	f[k][w] = f[k-1][w];		f[k][w] = f[k-1][w];
	}		}
	}		}
	}		}
	printf("%d",f[k-1][w-1]);		printf("%d",f[k-1][w-1]);

	return 0;		return 0;
	}		}

imported>jereneal at 11:59, 11 July 2013

2013-07-11T11:59:00Z

← Older revision		Revision as of 11:59, 11 July 2013
Line 2:		Line 2:
	* Extremely simple, but hard to understand		* Extremely simple, but hard to understand
	* Using DP		* Using DP
			* Can load same items several time
	#include <stdio.h>		#include <stdio.h>
	#include <stdlib.h>		#include <stdlib.h>

imported>jereneal at 11:55, 11 July 2013

2013-07-11T11:55:18Z

New page

= 0/1 KnapSack problem =
* Extremely simple, but hard to understand
* Using DP
#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;
}