Dp基础 简单背包问题
  anLrwkgbyYZS 2023年12月30日 8 0


背包问题大意:给你一个背包有一定的容量,再给你一下些物品,物品有自己的体积和价值,请你选择价值和最大的一些物品(最体积不超过背包的容量)

 

背包问题思路:逐渐放每一个物品,找到当前体积的最大价值。

           背包问题的主要代码

   

for(i=1;i<=n;i++)  //逐渐放一个物品
      for(j=m;j>=w[i];j--)  // 枚举背包放下这个物品的情况,j为背包的体积,当j<w[i] 背包放不下这个物品,所以不考虑这种情况
        {
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]); // 比较当前背包体积为j的价值 与 背包体积为j-w[i](这个物品的体积) 的价值加上这个物品的价值
   }
#include<stdio.h>
#include<string.h>
const int M=13000;  // 背包的最大体积(不同题不一样)
const int N=3500;  // 物体数量(也与题目给的范围有关)
int w[N], v[N];   //w[N] 存储物体的重量(体积)  v[N]存储物体的价值
int dp[M];       // 体积的最优解
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
int main()
{
    int i, j, n, m;
    scanf("%d %d",&n,&m);// n:物品的数量  m:背包的体积
    for(i=1; i<=n; i++)
    {
        scanf("%d %d",&w[i],&v[i]);
    }
    memset(dp,0,sizeof(dp));

    for(i=1; i<=n; i++)
        for(j=m; j>=w[i]; j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    printf("%d\n",dp[m]);
    return 0;
}

 

 

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS