首页 > 代码库 > poj 2063 基础完全背包

poj 2063 基础完全背包

这是一题基础的完全背包,适合初学者来理解完全背包


题意:有 n 种债券可以买 ,  每种债券的价格为 w , 每一年的收益为 p , 给你 wi 块钱 , 和 years 年的时间 , 我们最大的收益是是多少?


因为 , 每种债券可以买任意多个 , 所以这是一个简单的完全背包,但是由于基数(体积)太大 , 所以需要优化一下 :

由题意我们知道 , 每种债券的价格都是 1000 的倍数 , 那么我们就让每种债券的价格都 除以 1000 , 并且把 p 也除以 1000 , 这样就MTE , 也不会超时了。


完全背包和0---1背包

完全背包的每种物品是可以任意取多个 , 因此时间复杂为:O(VN(v/w1+v/w2........+v/wn)), 如果以这样的时间复杂度去A这题,那么就会超时。

优化:

完全背包每次可以取任意多个物品 , 因此我们这样看,当我们要去 n 物品时 , 让其和取 n-1 个物品时的状态,进行状态转移,也就是我们在状态转移时,我们从小到大进行转移。具体看下面代码。


代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define maxn 45011
long long w , d;
long long wi[300] , pi[300];
long long n ;
long long dp[maxn];

int main()
{
    int t;

    scanf("%d" , &t);
    while(t--)
    {
        cin>>w>>d;
        long long x , y , z;
        long long i , j;
        long long k = 1;
        long long sum = w;
        memset(dp , 0 , sizeof(dp));
        cin>>n;
        for(i = 1; i <= n; i++)
        {
            cin>>wi[i]>>pi[i];
            wi[i] /= 1000;
        }
        y = 0;
        for(z = 0; z < d; z++)
        {
            w = sum/1000;
            for(i = 1; i <= n; i++)
            {
                for(j = wi[i]; j <= w; j++)
                    dp[j] = max(dp[j] , dp[j-wi[i]] + pi[i]);//和0---1背包正好相反
            }
            sum += dp[w];
        }
        cout<<sum<<endl;
    }
    return 0;
}