关于背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。
                                                                                                                                                   ——搜狗百科

背包问题分为以下几类

#1 01背包

定义:01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。

标程:

#include<iostream>
using namespace std;
int dp[1001][1001],w[1001],v[1001],n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(j>=w[i])
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    cout<<dp[n][m]<<endl;
    return 0;
}

模板题:![]()

12-18 07:10
查看更多