[알고리즘]배낭 채우기
- 최초 등록일
- 2005.11.23
- 최종 저작일
- 1997.01
- 3페이지/ C언어
- 가격 4,900원
소개글
자료에 무게와 가치를 입력 받아 최고의 가치를 얻어 내는 프로그램 입니다.
알고리즘 시간에 많이 나오죠
목차
없음
본문내용
#include<stdio.h>
#include<stdlib.h>
void check_point(int n,int w,int** P,const int *weight); //동적 계획법 개선 함수
int maximum(int a, int b); //큰값을 출력 하는 함수
void knapsack(int n,int w, int **P,int *value,int* weight);//배낭 채우기 알고 리즘 함수
int main(void)
{
int n,w,**p,*value,*weight; //n항의 갯수 w총 무게 vlaue값 weight무게
int i,j; //카운트 변수
printf(" ***************************\n");
printf(" 아이템의 갯수와 무게를 입력\n");
printf(" ***************************\n");
printf("\n항의 갯수 입력 \n");
scanf("%d",&n);
printf("총 무게 입력 \n");
scanf("%d",&w);
p=(int**)malloc(sizeof(int)*(n+1)); //p[int*]형 동적 할당
value=(int*)malloc(sizeof(int)*(n+1)); //value[] 동적 할당
weight=(int*)malloc(sizeof(int)*(n+1)); //weight[] 동적 할당
for(i=0;i<=n;i++)
{
p[i]=(int*)malloc(sizeof(int)*w); //p[int*] -> [] 동적 할당
}
for(i=0;i<=n;i++) //각 배열 초기값 0 입력
{
value[i]=0;
weight[i]=0;
for(j=0;j<=w;j++)
{
p[i][j]=0;
}
}
printf(" ******************************\n");
printf(" 아이템 순서별 값과 무게를 입력\n");
printf(" ******************************\n");
for(i=0;i<n;i++) //값과 무게 입력 받음
{
printf("값[%d]입력\n",i+1);
scanf("%d",&value[i]);
printf("무게[%d]입력\n",i+1);
scanf("%d",&weight[i]);
참고 자료
없음