ACwing #3. 完全背包問題

完全背包問題和01背包問題很相似。
01背包問題每個物品只能選一個，而完全背包問題每個物品可以選無限次。

DP問題的關(guān)鍵是找到狀態(tài)轉(zhuǎn)移方程：

①定義f[i][j]表示從前 i 個物品中選擇,體積為 j 的時候的最大價值。
②那么轉(zhuǎn)移方程f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]],f[i - 1][j - 2 * v[i]],.....,f[i - 1][j - k * v[i]],....)

因此代碼就是：

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = 1 ; j<=m ;j++)
    {
        for(int k = 0 ; k*v[i]<=j ; k++)
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    }

    printf("%d",f[n][m]
    return 0;
}

由于數(shù)據(jù)量級的原因，此代碼肯定會發(fā)生TLE，因此需要進(jìn)行優(yōu)化。

f[i , j ] = max( f[i-1,j] , f[i- 1,j - v[i]+ w[i] , ?f[i - 1,j-2 * v[i]]+2 * w[i] , f[i -1,j - 3 * v[i]]+3 * w[i] , .....)
f[i , j - v[i]]= max( ? ? ? f[i - 1,j - v[i]] ,? ? ? ? ?f[i - 1,j - 2 * v[i]] + w[i]?, f[i - 1,j- 3 * v[i]]+2 * w[i]?, .....)

由上兩式，可得出如下遞推關(guān)系：?
? ? ? ? ? ? ? ? ? ? ? ? f[i][j]=max(f[i, j - v[i] ] + w[i] , f[i - 1][j])??

因此優(yōu)化后的代碼變?yōu)椋?/p>

#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  
  for(int i = 1;i <= n;i++){
      scanf("%d%d",&v[i],&w[i]);
  } 
  for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++){
      f[i][j] = f[i - 1][j];
      if(j >= v[i])
        f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);
    }
    
  printf("%d",f[n][m]);
  return 0;
}

? ? ? ? 可以看出代碼與01背包非常相似,因此嘗試能否做進(jìn)一步優(yōu)化。

優(yōu)化完成后的狀態(tài)轉(zhuǎn)移方程：f[j] = max(f[j], f[j - v[i]] + w[i])?

代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-418149.html

#include <iostream>
using namespace std;

const int N=1010;
int v[N],w[N],f[N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);  
  for(int i = 1;i <= n;i++){
      scanf("%d%d",&v[i],&w[i]);
  } 
  for(int i=1;i<=n;i++)
    for(int j=v[i];j<=m;j++){
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }    
  printf("%d",f[m]);  
  return 0;
}

到了這里，關(guān)于動態(tài)規(guī)劃：完全背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！