codevs 2033 邮票 （背包）&& codevs 1047 邮票面值设计 （dfs+dp）

6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1

5 2
1 3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e8;
int dp[maxn], a[55];
int main()
{
int k, n;
cin >> k >> n;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a+1, a+1+n);
for(int i = 1; ; i++)
//从1开始，因为他是说从1连续到m，如果1满足不了就输出0；
{
dp[i] = maxn; //这里一定要赋值无穷大，这样如果前面无法拼成，后面也可以直接输出
for(int j = 1; j <= n; j++)
{
if(a[j] > i) break;
dp[i] = min(dp[i-a[j]]+1,dp[i]);
}
if(dp[i] > k)
{
cout << i-1 << endl;
return 0;
}
}
return 0;
}

转自：http://blog.csdn.net/y1196645376/article/details/42197485

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e7 + 5;
int n, k, a[50], ans[50], max1, dp[maxn];
void get_dp()
{
for(int i = 1; ; i++)
{
dp[i] = maxn;
for(int j = 1; j <= k; j++)
{
if(a[j] > i) break;
dp[i] = min(dp[i], dp[i-a[j]]+1);
}
if(dp[i] > n)
{
if(i-1 > max1)
{
max1 = i-1;
for(int l = 1; l <= k; l++)
ans[l] = a[l];
}
return;
}
}
}
void dfs(int s)
{
if(s == k+1)
{
get_dp();
return;
}
for(int i = a[s-1]+1; i <= a[s-1]*n+1; i++)
{
a[s] = i;
dfs(s+1);
}
}
int main()
{
cin >> n >> k;
max1 = 1;
a[1] = 1;
dfs(2);
for(int i = 1; i <= k; i++)
printf("%d%c", ans[i], i == k ? 'n':' ');
printf("MAX=%dn", max1);
return 0;
}

转自：http://www.cnblogs.com/c1299401227/p/5573761.html

/*
这个题目知道是深搜，但是邮票面值的上界在深搜中不好确定，只知道下界是>前一个，这里就妙在用DP解决了深搜的上界，和当前邮票可以取到的连续最大值
*/
/*
①搜索。对每一步，枚举邮票面值，然后搜索下一张邮票面值并更新最优解。
②完全背包确定搜索范围。
假设现在枚举到第 i 张邮票面值，第 i-1 张邮票面值为a[i-1]，前 i-1 张邮票得到的最大连续值为x，则第 i 张邮票面值的范围就为 [a[i-1]+1，x+1]；
假设现在有 n 张邮票，怎么得到其最大连续值呢？
用 f[i] 记录达到数值 i 所需的最小邮票数量，初始化为一个极大值。然后用完全背包算出 f[i] 的值，从 0 开始，第一个f[i]>n，则 i-1 就为最大连续值。
*/
#define N 50
#include<iostream>
using namespace std;
#define inf 500
#include<cstdio>
#include<cstring>
int b[N],ans=0,a[N],f[inf];
int n,k;
void dfs(int m)
{
memset(f,0x3f,sizeof(f));
f[0]=0;
int i;
for(i=1;i<=inf;++i)
{
for(int j=1;j<=m&&a[j]<=i;++j)
f[i]=min(f[i],f[i-a[j]]+1);/*完全背包是可以把物品空间的内外循环交换位置的，反正都是无限放*/
if(f[i]>n)/*当前m种邮票所能取到的最大值*/
{
i--;
if(i>ans)
{
ans=i;
for(int l=1;l<=m;++l)
b[l]=a[l];
}
break;
}
}
if(m==k) return;
for(int j=i+1;j>a[m];--j)
{/*下一张邮票的范围*/
a[m+1]=j;
dfs(m+1);
}
}
int main()
{
scanf("%d%d",&n,&k);
a[1]=1;
dfs(1);
for(int i=1;i<=k;++i)
printf("%d ",b[i]);
printf("n");
printf("MAX=%dn",ans);
return 0;
}

最后

以上就是背后裙子为你收集整理的codevs 2033 邮票 （背包）&& codevs 1047 邮票面值设计 （dfs+dp）的全部内容，希望文章能够帮你解决codevs 2033 邮票 （背包）&& codevs 1047 邮票面值设计 （dfs+dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。