wordpress手机验证免插件seo搜索优化网站推广排名

题意：
一段很长的旅程，你有 一个 N 分钟的磁带，但是你喜欢的歌曲都在CD里 ，
你需要把CD的歌曲都录进磁带，问放哪些歌曲可以尽可能的利用磁带空间。
输入 磁带容量 N 和 歌曲数量 x ，接下来 x 个数表示每首歌曲的时长。
输出是哪些歌曲，和总时长。

 

解题：

0-1背包呀，就可以求出来最多可以放多少首进去了。
然后另外用一个数组 记录 背包容量为 j 时放进了第几件物品，就可以输出辣。
最先数组不够大 RE 辣

2333虽然简单题但是自己写出来还是很兴奋啊

 

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 100010;
const int INF = 0x3f3f3f3f;int d[maxn],a[100],p[maxn];int main()
{int n, num;while (scanf ("%d", &n) != EOF) {scanf ("%d", &num);for (int i = 1; i <= num; i ++) {scanf ("%d", &a[i]);}int d[maxn] = {0}, p[maxn] = {0};for (int i = 1; i <= num; i ++) {for (int j = n; j >= a[i]; j --) {if(d[j-a[i]] + a[i] > d[j]) {d[j] = d[j-a[i]] + a[i];p[j] = i;}}}int i = d[n], cnt = 0,ans[100] = {0};while (i > 0) {ans[cnt++] = a[p[i]];i = i - a[p[i]];}for (int j = cnt-1; j >= 0; j --)printf ("%d ",ans[j]);printf ("sum:%d\n",d[n]);}return 0;
}