背包問(wèn)題I

難度級(jí)別：B； 運(yùn)行時(shí)間限制：1000ms； 運(yùn)行空間限制：51200KB； 代碼長(zhǎng)度限制：2000000B

試題描述

??? 有一個(gè)背包容積為 V?和 n 個(gè)物品，并給出每個(gè)物品有一個(gè)體積。要求從 n 個(gè)物品中，任取若干個(gè)裝入背包內(nèi)，使背包的剩余空間為最小。

輸入

第一行兩個(gè)正整數(shù)?V?和?n，分別表示背包的容積和待裝物品的個(gè)數(shù)；第二行包括?n?個(gè)正整數(shù)，表示?n?個(gè)物品的體積，兩兩之間有一個(gè)空格分隔。

輸出

一個(gè)數(shù)，表示背包中剩余空間的最小值

輸入示例

24?6 8?3?12?7?9?7

輸出示例

0

其他說(shuō)明

數(shù)據(jù)范圍：0<V≤20000，0<n≤30

//============================================================================ // Name : maxsum.cpp // Author : judyge // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================/*** 動(dòng)態(tài)規(guī)劃:計(jì)算最大子段和* 算法描述:* 數(shù)組a 有n個(gè)元素, 記 s[i] 為從a【0】到a[i]中，包含a[i]的最大子段和* 則: s[i] 的值為: s[i-1]>0時(shí), s[i-1]+a[i]* 否則 a[i]*/ #include <stdio.h> #include <stdlib.h> #include <iostream> #include<algorithm> using namespace std;static int maxn[100]; //中間最大值保存在數(shù)組 static int j=0;int maxSub(int *a, int n,int v) {int i=0, max=0, max_pos = 0;int si_1=0, si = 0;//分別記錄s[i-1], 和 s[i]的值int *p = (int *)malloc(n*sizeof(int)); //p[i] 助于記錄哪些單元被選擇, p[i]=1 表示s[i]計(jì)算的結(jié)果中中使用了s[i-1]的值if (p==NULL)return -1;max = si_1 = a[0];p[0] = 0;for (i=1; i<n; i++){if (si_1<0){p[i] = 0;si = a[i];} else{p[i] = 1;si = si_1+a[i];}si_1 = si;if (si>max&&si<=v){ //小于等于背包V的保存在數(shù)組max = si;max_pos = i;maxn[j++]=max;}}//找到最大子段和的位置for (i=max_pos; i>=0; i--)if (p[i]==0)break;//即i..max_pos為最大子段和的元素printf("%d--%d:%d\n", i, max_pos, max);free(p);p = NULL;return max; }int main() {int n;int v;cin>>v>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}maxSub(a,n,v);sort(a,a+j); //排列cout<<a[j]; //輸出最大的 V的剩余最小return 0; }

總結(jié)

以上是生活随笔為你收集整理的背包问题I--最大字段和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。