题解 P1853 【投资的最大效益】

· · 题解

这道题是本蒟蒻刷过最水的背包题（小声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）