背包问题I--最大字段和

背包问题I

难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

有一个背包容积为 V 和 n 个物品，并给出每个物品有一个体积。要求从 n 个物品中，任取若干个装入背包内，使背包的剩余空间为最小。

输入

第一行两个正整数 V 和 n，分别表示背包的容积和待装物品的个数；第二行包括 n 个正整数，表示 n 个物品的体积，两两之间有一个空格分隔。

输出

一个数，表示背包中剩余空间的最小值

输入示例

24 6 8 3 12 7 9 7

输出示例

0

其他说明

数据范围：0<V≤20000，0<n≤30

//============================================================================ // Name : maxsum.cpp // Author : judyge // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================/*** 动态规划:计算最大子段和* 算法描述:* 数组a 有n个元素, 记 s[i] 为从a【0】到a[i]中，包含a[i]的最大子段和* 则: s[i] 的值为: s[i-1]>0时, s[i-1]+a[i]* 否则 a[i]*/ #include <stdio.h> #include <stdlib.h> #include <iostream> #include<algorithm> using namespace std;static int maxn[100]; //中间最大值保存在数组 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]计算的结果中中使用了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的保存在数组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; }

总结

以上是生活随笔为你收集整理的背包问题I--最大字段和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。