动态规划—(背包问题)

简介: 动态规划—(背包问题)

动态规划与其他算法比较,大大减少了计算量,丰富了计算的结果,最适合解决最优解问题。今天讲的是背包问题。

1、0-1背包:

简介:有n件物品,总空间是w,前i件的容量是w[i],前i件的价值是v[i],那么所获取的最大容量是dp[w].

代码如下:

#include<stdio.h>
#include<string.h>
int f[201000];
int w[210000];
int v[210000];
int max(int n,int m)
{
  if(n>m)
    return n;
  else
    return m;
}
int main()
{
    int n,m;
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
      memset(f,0,sizeof(f));
      for(i=1;i<=n;i++)
          scanf("%d%d",&w[i],&v[i]);
      for(i=1;i<=n;i++)
          for(j=m;j>=w[i];j--)
          {
             int s=f[j-w[i]]+v[i];
             f[j]=max(f[j],s);
          }
      printf("%d\n",f[m]);
  }
    return 0;
}

2、完全背包:

简介:完全背包是有n种物品,总空间为w,每种的物品的件数是无限个,已知每种物品的容量为w[i],价值为v[i],如何满足最大价值。

代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
int a[600],b[600],dp[1000005];
int main()
{
    int t,x,y,n;
    cin>>t;
    while(t--){
        int w;
        cin>>w;   //背包容量
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>b[i]>>a[i];
        for(int i=0;i<=w;i++)  //初始化分两种情况:1、如果背包要求正好装满则初始化 f[0] = 0,  f[i]=INF;2、如果不需要正好装满 f[0~w] = 0; 
            dp[i]=0;
        for(int i=0;i<n;i++)
           for(int j=b[i];j<=w;j++)//j表示背包容量 
                dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
   // for(int i=1;i<=w;i++)
        cout<<dp[w]<<endl;
    }
    return 0;
}

3、多重背包:

简介:多重背包就是0-1背包的扩展,0-1背包每一种物品一共有一件,多重背包每一种可能有多件,如一共有n种物品,每种物品的件数是bag[i],总空间是w,每一件容量是w[i],每一件价值是v[i].

代码如下:

#include<iostream>
#include<string.h>
#include <algorithm>
int v[1000],w[1000],c[1000],dp[1000];
using namespace std;
int main()
{
  int T;
  cin>>T;
  while(T--)
  {
    memset(dp,0,sizeof(dp));
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
      cin>>v[i]>>w[i]>>c[i];
    for(int i=1;i<=m;i++)
      for(int k=1;k<=c[i];k++)
        for(int j=n;j>=v[i];j--)
          dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[n]<<endl;
  }
  return 0;
}
目录
打赏
0
0
0
0
63
分享
相关文章
|
8月前
|
C++
每日练习之——背包问题
每日练习之——背包问题
42 1
背包问题之贪心算法
背包问题之贪心算法
104 0
动态规划之背包问题
动态规划之背包问题
109 0
【33. 0 1 背包问题】
背包问题 - 一共有N件物品,背包容量为V,物品有俩个属性,一个是体积一个是价值(类似在一个宝岛上,你有一个背包,它只能装满这个背包,小岛上有很多金子,各种体积的,而且每个金子纯度不一样,看最后怎么装才会使得背包中的金子价值最高) **四种背包问题** - 0 1 背包 每件物品最多只用一次, - 完全背包 每件物品有无线个 - 多重背包 每个物品不一样,每个物品最多有有S<sub>i</sub>个——朴素版和优化版 - 分组背包 有水果,汽车,人等,每一种里面最多只能选择一个
173 0
【33. 0 1 背包问题】
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等