hdu2159“FATE”完全背包

本文主要是介绍hdu2159“FATE”完全背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hdu2159“FATE”完全背包

一、什么是完全背包

有这样一个问题：

在你面前放着n种宝石，每种宝石重量为wi，价值为vi，数量无限；你有一个最多可以放m重量的背包。现在你想在不超重的情况下，是你带走的宝石价值最大，问最大价值是多少？

在这里，“完全”是指每一种宝石都有无数个，不是指背包能装多少物品（不是背包的属性）。
dp用于保存背包的状态S（有某些必要的维度，如容量等）
注意：在某一背包容量下的最大价值不一定是完全利用背包容量的！！！

二、代码

写了两个代码，注意区别：dp表示状态的方式不同。初始化的不同。

代码一：复杂度O(k*m)

这里只用一个维度维护背包的容量，而每一个状态dp(S)总内含对应背包状态的装载个数。

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const int maxn = 1e2;
struct S//状态：
{int v; //最大经验int cot;//杀死怪物数
};
S dp[maxn];//dp[c]：忍耐值为c时,获得的最大经验为dp[c].v，此时杀怪数为dp[c].cot；
struct Node//怪
{int w;//减少的忍耐度int v;//经验
};
Node node[maxn]; //保存输入的怪
//hdu2159
int n, m, k, s;//需要经验，忍耐度， 怪物种类， 最大杀怪数void scaner()
{for(int i = 0; i < k; i++){//输入怪的类型scanf("%d %d", &node[i].v, &node[i].w);//cout << "node[i].v:" << node[i].v << " node[i].w:" << node[i].w << endl;}
}void solve()
{//初始化：杀了0只怪 且 背包容量为0时，杀怪数和获得经验都为0.for(int i = 0; i <= m; i++){//背包容量dp[i].v = dp[i].cot = 0;}//递推for(int i = 0; i < k; i++){//每一种怪物for(int c = node[i].w; c <= m; c++){//背包维度if(dp[c-node[i].w].cot < s && dp[c].v < node[i].v + dp[c-node[i].w].v){//目前状态可以杀怪且杀了更多经验dp[c].v = dp[c-node[i].w].v + node[i].v ;dp[c].cot = 1 + dp[c-node[i].w].cot;}}}
//    for(int i = 0; i <= m; i++)
//        cout << dp[i].v << " " << dp[i].cot << endl;
//    cout << endl;
}int ans()
{for(int i = 0; i <= m; i++){if(dp[i].v >= n){return m - i;}}return -1;
}int main()
{//freopen("in.txt", "r", stdin);while(~scanf("%d %d %d %d", &n, &m, &k, &s)){scaner();solve();printf("%d\n", ans());}return 0;
}

代码二：复杂度O(ksm)

这里dp有两个维度，容量和装载数。这样就导致了某些状态因为可装载数不可能实现而导致dp表中的状态不可能存在。根据题意，不可能存在的状态可用-1表示。（注意初始化）
在代码一种，dp种所有状态都存在。

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const int maxn = 1e2;
int dp[maxn][maxn]; //dp[i][c]杀怪数为i,忍耐度为c，最大获得经验
struct Node//怪
{int w;//忍耐度int v;//经验
};
Node node[maxn]; //保存输入的怪
//hdu2159
int n, m, k, s;//需要经验，忍耐度， 怪物种类， 最大杀怪数void scaner()
{for(int i = 0; i < k; i++){//输入怪的类型scanf("%d %d", &node[i].v, &node[i].w);//cout << "node[i].v:" << node[i].v << " node[i].w:" << node[i].w << endl;}
}void solve()
{//初始化for(int i = 0; i <= s; i++){//怪的数量for(int j = 0; j <= m; j++){//背包容量dp[i][j] = -1; //-1表示该状态不存在}}//杀了0只怪时for(int i = 0; i <= m; i++){dp[0][i] = 0;}//递推for(int i = 0; i < k; i++){//怪的维度for(int j = 1; j <= s; j++){for(int c = node[i].w; c <= m; c++){//背包容量if(dp[j-1][c-node[i].w] != -1){//当有前一个状态时才能择其大的方案dp[j][c] = max(dp[j][c], dp[j-1][c-node[i].w] + node[i].v);}//若没有前一个状态则保持原状}}}//    cout << "s = " << s << " m = " << m << endl;
//    for(int i = 0; i <= s; i++){
//        for(int j = 0; j <= m; j++){
//            cout << dp[i][j] << "\t";
//        }
//        cout << endl;
//    }}int ans()
{int ret = dp[0][0];for(int c = 0; c <= m; c++){for(int i = 0; i <= s; i++){if(dp[i][c] >= n){return m - c;}}}return -1;
}int main()
{//freopen("in.txt", "r", stdin);while(~scanf("%d %d %d %d", &n, &m, &k, &s)){scaner();solve();printf("%d\n", ans());}return 0;
}