[알고리즘]배낭 채우기

소개글

자료에 무게와 가치를 입력 받아 최고의 가치를 얻어 내는 프로그램 입니다.
알고리즘 시간에 많이 나오죠

목차

없음

본문내용

#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]);

참고 자료

없음