c 01背包 vs2022 源代碼

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

int main() {

//1.鍵盤錄入一個常量，用來表示  物品的種類，  n = 5；
//2.鍵盤錄入一個常量，用來表示  背包的容量，  c = 10；
//3.建立一個整型數組，用來收納 每個物品的重量，int weight[]; 資料：  1 4 2 5 2
//4.建立一個整型數組，用來收納 每個物品的價值， int value[]; 資料：  1 6 5 3 1
//5.建立一個函數，用來表示01背包的進行的過程。
int zero(int n, int c, int weight[], int value[]);//聲明函數

//1.鍵盤錄入一個常量，用來表示  物品的種類，  n = 5；

printf("請輸入物品的種類：");
int n=0;
scanf_s("%d", &n);

//2.鍵盤錄入一個常量，用來表示  背包的容量，  c = 10；

printf("請輸入物品的容量：");
int c=0;
scanf_s("%d", &c);

//3.建立一個整型數組，用來收納 每個物品的重量，int weight[];

printf("請輸入每個物品的重量：");
int weight[5] = { 0 };

int sz = sizeof(weight)/sizeof(weight[0]);
for (int i = 0; i < sz; i++) 
{
  scanf_s("%d", &weight[i]);
}


//4.建立一個整型數組，用來收納 每個物品的價值， int value[];
printf("請輸入每個物品的價值：");
int value[5] = { 0 };

int sz1 = sizeof(value) / sizeof(value[0]);
for (int i = 0; i < sz1; i++)
{
   scanf_s("%d", &value[i]);
}



int sb = zero(5, 10, weight, value);
 printf("%d", sb);

return 0;      

}

​​//5.建立一個函數​​，用來表示01背包的進行的過程。

int zero(int n, int c, int weight[], int value[])

{

int dp[6][11] = { 0 }; //數組使用時都要進行初始化。要不然容易報錯。

int Max(int a,int b);//聲明函數

for (int i = 1; i <=n; i++) 
{
  int w1 = weight[i - 1];
  int v = value[i - 1];

  for (int j = 1; j <= c; j++) 
  {
    if (j < w1) 
    {
      dp[i][j] = dp[i - 1][j];
      continue;
    }
    else 
    {
      dp[i][j] = Max(dp[i - 1][j], dp[i - 1][j - w1] + v);
    }
  }
}

return dp[n][c];      

}

int Max(int a, int b)

{

if(a>=b)
{
  return a;
}
else
{
  return b;
}      

}

/二維數組使用時都要進行初始化。要不然容易報錯。