01背包 与 emo题目背景（周超人的遗憾） 的爱恨情仇

本题背景有意思，大家当乐子看，目前没有找到题目原题，也没有写过完全是01背包模板的题目，该篇文章大家注意其01背包一维写法的模板就好，注意各个关键点

我会陆续发布算法题题解，感兴趣的可以关注哦

01-背包周超人唯一的遗憾

前景提要

“家人们谁懂啊，那个虾头男，一下子给我们好多人送了好多情书”

那天znz回到协会，协会里所有的人便看着笑，有的叫：“znz你怎生的如此失落”，znz不回答，对尹神说：“找两道算法题，再要一道2000分的思维题”，便打开sublime text。他们又故意喊道：“你一定是又被人家拒绝了！”znz睁大眼睛说，“你怎么这样凭空污人清白……”“什么清白?我前天亲眼见你给ofgg去送情书，后来抱头痛哭。”znz便涨红了脸，额上的青筋条条绽出，争辩道，“谈恋爱你情我愿的事，说不上拒绝！谈恋爱的事，能算虾头吗？”接连便是难懂的话，什么“他说我是个好人”，什么“可惜我们不合适”之类，引得众人都哄笑起来，协会内外充满了快活的气息

题目描述

深夜漫漫，距离天亮还有V分钟，znz很难受睡不着，决定启动网易云音乐，目前他的歌单里面有n首歌。每首歌都有一个时间。现在znz决定从这n首歌中任选若干个来听（同时每首歌最多只能听一遍），使得听完后距离天亮的时间最短（但是不能超过天亮的时间），输出这个距离天亮最短的时间。

输入描述

第一行共一个整数 V，表示距离天亮的时间。

第二行共一个整数 n，表示歌单中歌曲的数量。

接下来 n 行，每行有一个正整数，表示第 i 首歌的时间。

输出描述

共一行一个整数，表示距离天亮最短剩余时间。

样例 1

数据范围

对于 100%数据，满足 0≤<n≤30，1≤V≤20000。

题目背景

整个学校都休息了，只剩下我的我的心事，夜不能寐。 整个城市都睡觉了，只剩下我和我的遗憾，掀起波涛。 当年我在非洲当雇佣兵的时候，每天坚持用小口径子弹打自己，日复一日，年复一年，终于练成了金钟不坏之身。后来成为兵王回国，遇见了她，才知道，有些人有些事，是由内而外的破防。躲过了战场上的枪林弹雨，却没能躲过你的万箭穿心。

分析：

为什么是01背包呢？

因为题目这样子写的啊！ 因为最多只能放一遍----->01背包

背包：距离天亮的时间 物品：歌曲的时间

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>/*max函数所在头文件*/

#define quickio ios::sync_with_stdio,cin.tie(0),cout.tie(0);

using namespace std;

//01-背包周超人唯一的遗憾

//背包：距离天亮的时间
//物品：歌曲的时间
//因为最多只能放一遍----->01背包

//Runtime Error on test 2不是超时

#include <climits>
const int MAX = 20005;

int main()
{
	quickio;

	int V;
	cin >> V;

	int n, t[35] = { 0 }, dp[MAX] = { 0 };
	cin >> n;

	int i;
	for (i = 0; i < n; i++)
	{
		cin >> t[i];
	}


	int j;
	for (i = 0; i < n; i++)
	{
		for (j = V; j >= t[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - t[i]] + t[i]);
		}
	}

	cout << V - dp[V] << endl;
	return 0;
}

最后祝大家题题AC，只盼做个WA梦 ~