C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法

更新時(shí)間：2015年04月20日 12:21:11 作者：司青

這篇文章主要介紹了C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法,實(shí)例分析了背包問(wèn)題的原理與C++實(shí)現(xiàn)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法。分享給大家供大家參考。具體分析如下：

問(wèn)題描述：

背包的最大容量為W,有N件物品，每件物品重量為w,價(jià)值為p，怎樣選擇物品能使得背包里的物品價(jià)值最大？

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

實(shí)現(xiàn)代碼：

#include <stdio.h>
#define THING  20
#define WEIGHT 100
int arr[THING][WEIGHT];
/* 背包容量為weight，依次嘗試1 - thing 物品時(shí)的最大價(jià)值 */
int price[100]; /* 物品價(jià)格表 */
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;
 }
  /* 讀入數(shù)據(jù) */
 scanf("%d%d",&max_weight,&max_thing);
 for(i = 1 ; i <= max_thing ; ++i)
 {
 scanf("%d%d",&weight[i],&price[i]);
 }
  /* 計(jì)算 */
 for(i = 1 ; i <= max_thing ; ++i)
 {
 for(j = 1 ; j <= max_weight ; ++j)
 {
  if(j >= weight[i])
  /* 如果當(dāng)前物品的容量小于背包容量
  （當(dāng)前物品能放進(jìn)去） */
  {
  /* 如果當(dāng)前物品的價(jià)值 + 背包剩余空間能放進(jìn)去的物品價(jià)值
  (之間計(jì)算過(guò)的最佳方案) */
  /* 大于上一次選擇的價(jià)值，則放入當(dāng)前物品 */
  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 /* 否則繼續(xù)沿用上次的選擇 */
   arr[i][j] = arr[i - 1][j];
  }
  else /* 當(dāng)前物品放不進(jìn)去，繼續(xù)沿用上次的選擇 */
  arr[i][j] = arr[i - 1][j];
 }
 }
  /* 輸出最優(yōu)解 */
 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;
}

希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。

您可能感興趣的文章:

相關(guān)文章

C++控制臺(tái)實(shí)現(xiàn)隨機(jī)生成路徑迷宮游戲
這篇文章主要為大家詳細(xì)介紹了C++控制臺(tái)實(shí)現(xiàn)隨機(jī)生成路徑迷宮游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-05-05
基于QT實(shí)現(xiàn)自定義溫度計(jì)的示例代碼
QT原生控件沒(méi)有實(shí)現(xiàn)如儀表盤(pán)或者溫度計(jì)的控件,只好自己實(shí)現(xiàn),所以本文為大家介紹了如何利用qt實(shí)現(xiàn)自定義溫度/濕度控件,感興趣的小伙伴可以了解下
2023-11-11
C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法
這篇文章主要介紹了C++實(shí)現(xiàn)當(dāng)前時(shí)間動(dòng)態(tài)顯示的方法,涉及C++時(shí)間操作及Sleep方法的使用,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-07-07
C++實(shí)現(xiàn)LeetCode(50.求x的n次方)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(50.求x的n次方),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
詳解C++的反調(diào)試技術(shù)與繞過(guò)手法
反調(diào)試技術(shù)，惡意代碼會(huì)用它識(shí)別自身是否被調(diào)試，或者讓調(diào)試器失效，給反病毒工程師們制造麻煩，拉長(zhǎng)提取特征碼的時(shí)間線(xiàn)，本章將具體總結(jié)常見(jiàn)的反調(diào)試基礎(chǔ)的實(shí)現(xiàn)原理以及如何過(guò)掉這些反調(diào)試手段，從而讓我們能夠繼續(xù)分析惡意代碼
2021-06-06
C++實(shí)現(xiàn)類(lèi)似延時(shí)停頓的打字效果
這篇文章主要介紹的是使用C++實(shí)現(xiàn)類(lèi)似延時(shí)停頓的打字效果的代碼，非常的簡(jiǎn)單，推薦給大家，有需要的小伙伴可以參考下。
2015-03-03
C++?和?C#?中的?lambda的方法技巧
這篇文章主要介紹了C++?和?C#?中的?lambda的方法技巧，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下
2022-06-06
C語(yǔ)言中continue的用法詳解
在C語(yǔ)言當(dāng)中的continue和break語(yǔ)句是有一些類(lèi)似的,但是它并不是強(qiáng)制進(jìn)行終止的,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中continue用法的相關(guān)資料,需要的朋友可以參考下
2022-11-11
C++ primer基礎(chǔ)之容器insert
這篇文章主要介紹了C++ primer基礎(chǔ)之容器insert的相關(guān)資料,需要的朋友可以參考下
2017-02-02
解析C++中的虛擬函數(shù)及其靜態(tài)類(lèi)型和動(dòng)態(tài)類(lèi)型
虛擬函數(shù)(Visual Function)亦常被成為虛函數(shù),是C++中的一個(gè)重要特性,本文我們就來(lái)解析C++中的虛擬函數(shù)及其靜態(tài)類(lèi)型和動(dòng)態(tài)類(lèi)型
2016-06-06