大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

DP-01背包问题

思路:dp[i][j]表示的是前i个物品背包所能容纳不超过bagw的最大价值.

成都创新互联是一家集网站建设,顺河企业网站建设,顺河品牌网站建设,网站定制,顺河网站建设报价,网络营销,网络优化,顺河网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。

#include
using namespace std;
const int maxn = 100;
int main()
{
    int n,bagw;
    int w[maxn],v[maxn];
    int dp[maxn][maxn];
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>w[i]>>v[i];
    }
    cin>>bagw;
    for(int i = 0; i < n; i++)   //初始化第一列(背包重为0时的最大价值) 
    dp[i][0] = 0;
    for(int j = 0; j <= bagw; j++)  //初始化第一行 
    {
        if(j >= w[0])
            dp[0][j] = v[0];
        else
            dp[0][j] = 0;
    }
    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= bagw; 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-01背包问题


网站栏目:DP-01背包问题
网页网址:http://dzwzjz.com/article/pgejhj.html
在线咨询
服务热线
服务热线:028-86922220
TOP