自动搬运

查看原文

来自洛谷，原作者为

	Sham_Sleep 希望你被簇拥包围，所以你走的路要繁花盛开，要人声鼎沸。

搬运于2025-08-24 21:31:06，当前版本为作者最后更新于2020-02-14 10:23:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题是本蒟蒻刷过最水的背包题（小声bb）

当本蒟蒻第一眼看到这道题的时候，满满文学气息铺面而来。

以本蒟蒻小学三年级的阅读水平，想要一次性完全看懂还是很难的。

所以我分了三次看：

1.这个题目不能将债券拆开来投资，也就是必须投整个进去。 （胖虎发现了不对劲）。也就是说，我们不能按照贪心的思路求单位价值再排序。

2.初步可以断定是dp了，但是，这个dp是将各种债券不停搭配来求到最值。也就是说这个dp是一个物品对应着一种阶段。并且求完之后还要再循环求下一年的。

3.那么可以确定他是背包了。他的数量是无限的。不同于选和不选。所以可以确定这是个完全背包题。

那么，这个题的主体代码就可以拆成两部分了——完全背包的模板+n次循环求解

也就是说，我们要将每一年得到的钱再加上本金，投入下一年的投资，这样才能实现最值（题目里没有限制，也就是说这样可以的）

至于有的同学没有学过背包，可以先到网上搜一下，本蒟蒻在这里贴出我写的01背包和完全背包

01背包

#include <stdio.h>
#include <iostream>
#include <map>
using namespace std;
int dp[1000000];
int w[100000];
int v[100000];
int main()
{
	int n,t;
	scanf("%d%d",&t,&n);
	for(int i=1; i<=n; i++){
		scanf("%d%d",&w[i],&v[i]);                                                           
	}
	for(int i=1; i<=n; i++){
		for(int j=t; j>=w[i]; j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d",dp[t]);
}

完全背包

#include <stdio.h>
#include <iostream>
using namespace std;
int dp[1000];
int w[1000];
int v[1000];
int m,n;
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1; i<=n; ++i){
		scanf("%d%d",&w[i],&v[i]);
	}
	for(int i=1; i<=n; ++i){
		for(int j=0; j<=m; ++j){
			if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("max=%d",dp[m]);
	return 0;
}

接下来，就上本题AC代码啦——

#include <stdio.h>
#include <iostream>
#include <memory.h>
using namespace std;
int w[100000];
int v[100000];
int dp[100000];
int s,n,d;
int main()
{
	scanf("%d%d%d",&s,&n,&d);
	for(int i=1; i<=d; ++i){
		scanf("%d%d",&w[i],&v[i]);
	}
	for(int i=1; i<=n; ++i){
		int m=s/1000;
		for(int j=1; j<=d; ++j){
			for(int k=w[j]/1000; k<=m; ++k){
				if(k>=w[j]/1000) dp[k]=max(dp[k],dp[k-w[j]/1000]+v[j]);
//				printf("%d ",dp[k]);
			}
//			printf("\n");
		}
		s+=dp[m];
		memset(dp,0,sizeof(dp));

	}
	printf("%d",s);
}

第二次写题解，支持一下本蒟蒻吧（QwQ）