成都青羊网站建设,潍坊品牌设计公司,网站建设属于什么行业分类,平面设计在哪里学文章目录 一、二维费用的背包问题二、潜水员三、机器分配四、开心的金明五、有依赖的背包问题 一、二维费用的背包问题
题目链接
#includeiostream
#includealgorithm
using namespace std;
const int M 110;
int n,m,kg;
int f[M][M];int main()
{cin iostream
#includealgorithm
using namespace std;
const int M 110;
int n,m,kg;
int f[M][M];int main()
{cin n m kg;for(int i 0;i n;i ){int v,M,w;cin v M w;for(int j m;j v;j --)for(int k kg;k M;k --){f[j][k] max(f[j][k], f[j - v][k - M] w);}}cout f[m][kg];return 0;
}二、潜水员
题目链接 题解来源小呆呆 , 这个题相较于二维费用的背包问题稍稍有一点改变二维费用的背包模板是体积不超过V重量不超过M但是这个题是体积至少为V重量至少为M。 对比两题的思路二维费用的背包问题求的是不能超过体积V重量M的情况下能拿到价值的最大值。而本题是至少需要体积V重量M的情况下能拿到价值的最小值。就拿体积来说至少需要多少体积也就是说有体积比需要的体积大的物品还是能用得到例如f[3][5]至少需要3个体积5个重量求能拿到价值的最小值现在只有一个物品体积是4重量是4价值w它说至少需要3个体积那么体积是4还是可以用到只是多了1个体积没用占着而已不影响其价值。因此若用了这个物品则变成了求f[0][1] w表示体积已经不再需求了只需要0个体积即可 #includeiostream
#includealgorithm
#includecstring
using namespace std;int n,m,k;
const int M 25, N 82;
int f[M][N];
const int INF 0x3f3f3f3f;int main()
{cin m n;cin k;memset(f, 0x3f, sizeof f);f[0][0] 0;for(int i 1;i k;i ){int a,b,c;cin a b c;for(int j m;j 0;j --)for(int x n;x 0;x --){f[j][x] min(f[j][x], f[max(0,j - a)][max(0, x - b)] c);}}cout f[m][n];return 0;
}三、机器分配
题目链接
#includeiostream
#includealgorithm
using namespace std;int n,m;
const int N 12, M 18;
int f[N][M];
int ne[M];
int w[N][M];
int way[M];int main()
{cin n m;for(int i 1;i n;i )for(int j 1;j m;j )cin w[i][j];for(int i 1;i n;i ){for(int j 0;j m;j ){for(int k m;k j;k --)f[i][k] max(f[i][k], f[i - 1][k - j] w[i][j]);}}cout f[n][m] endl;int j m;for(int i n;i 1;i --)for(int k 0;k m;k )if(f[i][j] f[i - 1][j - k] w[i][k]){way[i] k;j - k;break;}for(int i 1;i n;i ) cout i way[i] endl;return 0;
}四、开心的金明 这个题很容易就是一个01背包问题 #includeiostream
#includealgorithm
using namespace std;
const int N 30100;
int n,m;
int f[N];int main()
{cin n m;for(int i 1;i m;i ){int v,w;cin v w;for(int j n;j v;j --)f[j] max(f[j], f[j - v] v * w);}cout f[n];return 0;
}五、有依赖的背包问题
题目链接
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N 110;
int head[N],e[N],ne[N],idx;
int n,m;
int v[N],w[N],p;
bool st[N];
int f[N][N];void add(int a,int b)
{e[idx] b, ne[idx] head[a], head[a] idx ;
}void dfs(int u)
{for(int i head[u]; ~i;i ne[i]){int son e[i];dfs(e[i]);for(int j m - v[u];j 0;j --){for(int k 0;k j;k )f[u][j] max(f[u][j], f[u][j - k] f[son][k]);}}for(int i m;i v[u];i --) f[u][i] f[u][i - v[u]] w[u];for(int i 0;i v[u];i ) f[u][i] 0;
}int main()
{cin n m;memset(head, -1,sizeof head);int root;for(int i 1;i n;i ){cin v[i] w[i] p;if(p -1) { root i;continue;}add(p, i);st[i] true;}dfs(root);cout f[root][m];return 0;
}
