当前位置：网站首页>ACM01背包问题

ACM01背包问题

2022-08-09 11:02:00 【抓个马尾女孩】

问题描述：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。

#include<iostream>
using namespace std;
const int maxn=2000;
int a[maxn][maxn],w[maxn],c[maxn];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i=i+1)
    cin>>w[i]>>c[i];
    for(int i=1;i<=m;i=i+1)
        for(int v=n;v>0;v=v-1)
        {
        if(w[i]<=v) a[i][v]=max(a[i-1][v],a[i-1][v-w[i]]+c[i]);
        else a[i][v]=a[i-1][v];
        }
    cout<<a[m][n]<<endl;
    return 0;
}
原网站

版权声明
本文为[抓个马尾女孩]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_44563460/article/details/89045325

边栏推荐

猜你喜欢

随机推荐