C++靜態計劃之背包成績處理辦法

C++靜態計劃之背包成績處理辦法。本站提示廣大學習愛好者：（C++靜態計劃之背包成績處理辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++靜態計劃之背包成績處理辦法正文

本文實例講述了C++靜態計劃之背包成績處理辦法。分享給年夜家供年夜家參考。詳細剖析以下：

成績描寫：

背包的最年夜容量為W,有N件物品，每件物品分量為w,價值為p，如何選擇物品能使得背包裡的物品價值最年夜？

輸出：
10 3   (W,N)
4 5   (w,p)
6 7   (w,p)
8 9   (w,p)

完成代碼：

#include <stdio.h>
#define THING  20
#define WEIGHT 100
int arr[THING][WEIGHT];
/* 背包涵量為weight，順次測驗考試1 - thing 物品時的最年夜價值 */
int price[100]; /* 物品價錢表 */
int weight[100]; /* 物品分量表 */
 int main()
{
 int i,j;
 int max_weight,max_thing;
  /* 初始化 */
 for(i = 0 ; i < THING ; ++i)
 {
 for(j = 0 ; j < WEIGHT ; ++j)
  arr[i][j] = 0;
 }
  /* 讀入數據 */
 scanf("%d%d",&max_weight,&max_thing);
 for(i = 1 ; i <= max_thing ; ++i)
 {
 scanf("%d%d",&weight[i],&price[i]);
 }
  /* 盤算 */
 for(i = 1 ; i <= max_thing ; ++i)
 {
 for(j = 1 ; j <= max_weight ; ++j)
 {
  if(j >= weight[i])
  /* 假如以後物品的容量小於背包涵量
  （以後物品能放出來） */
  {
  /* 假如以後物品的價值 + 背包殘剩空間能放出來的物品價值
  (之間盤算過的最好計劃) */
  /* 年夜於上一次選擇的價值，則放入以後物品 */
  if(price[i] + arr[i - 1][j - weight[i]] > arr[i - 1][j])
   arr[i][j] = price[i] + arr[i - 1][j - weight[i]];
  else /* 不然持續沿用前次的選擇 */
   arr[i][j] = arr[i - 1][j];
  }
  else /* 以後物品放不出來，持續沿用前次的選擇 */
  arr[i][j] = arr[i - 1][j];
 }
 }
  /* 輸入最優解 */
 printf("max weight : %d\n",arr[max_thing][max_weight]);
  /* 輸入一切子解 arr[][] */
 for(i = 0 ; i <= max_thing ; ++i)
 {
 for(j = 0 ; j <= max_weight ; ++j)
  printf("%3d",arr[i][j]);
 printf("\n");
 }
  return 0;
}

願望本文所述對年夜家的C++法式設計有所贊助。