首页 > 代码库 > POJ 2063 Investment

POJ 2063 Investment

完全背包问题。


我的背包训练第二题。按照背包九讲的步骤来搞。


题意是说给你一些本钱,然后有一些债券可以购买,不同的债券会有不同的利润,在规定年限内,利润要最大。


债券是无限制购买的,(完全背包)获得的利润可以买债券,(背包变大)

每年都可以选择债券,也就是每年都要重新开始,(每年一次)

最后得出你手上的钱有多少。这道题题目中提示了 1000的倍数。但是本钱不一定,利润也不一定。

只有债券在输入时候可以除1000。每年开始的时候,本钱除1000,不过也要保存 %1000。


02(笑)背包的自我修养:


F[0…V ] ← 0
for i   ←    1 to N
    for v   ←    Ci to M
        F[v]   ←    max(F[v]; F[v - Ci] +Wi)


伪代码,跟01背包有点相似,也有点不同。


C[]表示费用,W[]表示价值。M表示背包容量


01背包的第二个过程是反过来的,从M → 0;为了保证在考虑“选入第i 件物品”这件


策略时,依据的是一个绝无已经选入第i 件物品的子结果F[i - 1; M - Ci]。


完全背包却可能某种物品选择多次。


int dp[1000001];
int c[100001],v[100001];


memset(dp,0,sizeof(dp));


for(int i=0;i<n;i++)
        {
            for(int j=c[i];j<=m;j++)
                dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
        }


已经坑到第二步,完全背包了。不过还得细细体会。

本题代码:


#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int dp[100001];
int c[11],v[11];
int main()
{
    int t,m,n,year;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&year);
        scanf("%d",&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&c[i],&v[i]);
            c[i]/=1000;
        }
        memset(dp,0,sizeof(dp));
        while(year--)
        {
            int tmp=n%1000;
            n/=1000;
            for(int i=0; i<m; i++)
            {
                if(c[i]>n)continue;
                for(int j=c[i];j<=n;j++)
                {
                    dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
                }
            }
            int ans=0;
            for(int i=0; i<=n; i++)
                ans=max(ans,dp[i]);
            n=n*1000+tmp+ans;
        }
        printf("%d\n",n);
    }
}