那年的埃菲尔

用户名：18839270274

访问量：19050

签　名：

我只是个蒟蒻(⊙o⊙);

等　　级
排　　名	190
经　　验	6652
参赛次数	1
文章发表	50
年　　龄	0
在职情况	学生
学　　校	郑州大学
专　　业	计算机科学与技术

　　自我简介：

欢迎加我QQ交流 540671670

TA的其他文章

连续自然数和-题解(C++代码)（简单解法）
浏览：165

诡秘的余数-题解(C++代码)
浏览：282

小O的溢出-题解(C/C++语言代码)（参考一下）
浏览：279

你可能喜欢

小O的溢出-题解(C/C++语言代码)（参考一下）

　　作者: 那年的埃菲尔　　　　发表时间：2020-02-20 17:33:32 浏览：279　|　评论：0　

原题链接：小O的溢出

#### 解题思路：
这是一道 0-1 背包的拓展问题，与常规 0-1 背包不同的是，“撑破背包的最后一件物品”可以带走。将问题转化为 0-1 背包的表述就是：

已知背包容量 V 和每件物品的体积，且：

若背包未满，则无论当前物品是否超过剩余容量，总可以装进去。
若背包已满或者已过载，则不能再放入物品。
问最多能带走多少体积的物品。

#### 参考代码：

```c
#include<stdio.h>
#include<stdlib.h>

int dp[101][10000] = { 0 };
int bigger(int i , int j)
{
	return i > j ? i : j;
}

int main()
{
	int n , m , i , j ;
	int v[100] = {0};	//C中没有迭代器 只能开辟一个数组空间
	while(scanf("%d%d" , &n , &m) != EOF)
	{
		int max;		//max储存最大的数
		scanf("%d",&max);
		int temp;
		for( i = 1 , j = 0 ; i < n ; i++)
		{
			scanf("%d" , &temp);
			if(temp > max)
			{
				v[j++] = max;
				max = temp;
			}
			else
				v[j++] = temp;
		}
		int	*it = v;		//用一个指针指向一个数组 方便遍历
		int item1 = *it;
		for( i = 1 ; i < m ; i++)	//初始化 dp 数组第一行
		{
			if(i >= item1)
				dp[1][i] = item1;
			else
				dp[1][i] = 0;
		}
			it++;
		for( i = 2 ; i < n ; i++ , it++)
		{
			int item = *it;
			for(j = 1 ; j < m ; j++)
			{
				if( j < item )
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = bigger(dp[i-1][j] , dp[i-1][j-item] + item);
			//递推计算 V-1 背包的最优解
			}
		}
		printf("%d\n" , dp[n-1][m-1] + max); 
	}
	return 0;
}
```

下面是用C++的语言写的 因为C++中有vector迭代器 所以不用开辟数组空间 比较灵活存n个数

```cpp
#include<bits/stdc++.h>
using namespace std;

int dp[101][10000] = { 0 };
int bigger(int i , int j)
{
	return i > j ? i : j ;
}

int main()
{
	int n , m ;
	while(cin >> n >> m)
	{
		vector<int> v ;
		int max ;
			cin >> max;
		int temp;
		for(int i = 1 ; i < n ; i++)
		{
			cin >> temp;
			if(temp > max)
			{
				v.push_back(max);
				max = temp;
			}
			else
				v.push_back(temp);
		}
		vector<int>::iterator it = v.begin();
		int item1 = *it;
		for(int i = 1 ; i < m ; i++)
		{
			if(i >= item1)
				dp[1][i] = item1;
			else
				dp[1][i] =0;
		} 
			it++;
		for(int i = 2 ; i < n ; i++ , it++)
		{
			int item = *it;
			for(int j = 1 ; j < m ; j++)
			{
				if(j < item)
					dp[i][j] = dp[i-1][j];
				else
					dp[i][j] = bigger(dp[i-1][j] , dp[i-1][j-item] + item);
			}
		}
		cout << dp[n-1][m-1] + max << endl; 
	}
	return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

那年的埃菲尔

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

母牛的故事（C语言代码）

C语言训练-排序问题<2> （C++代码）

小O的溢出-题解(C/C++语言代码)（参考一下）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

打印十字图（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

那年的埃菲尔

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-排序问题<2> （C++代码）

小O的溢出-题解(C/C++语言代码)（参考一下）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

打印十字图 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C二级辅导-公约公倍（C语言代码）

母牛的故事（C语言代码）

　　评论区

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

打印十字图（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）