动态规划01背包问题

时间:2022-02-25 15:45:36

 

问题描述:给定n种物品和一背包,物品i的重量是wi,其价值是pi,背包的容量是M,问如何选择装入背包中的物品总价值最大?

问题特点是:每种物品一件,可以选择放1或不放0。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,据说基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以详细的查了一下这个方程的含义:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

在有的地方看到的背包问题题目中,有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故仔细体会上面基本思路的得出方法,状态转移方程的含义。

       for(int i=1;i<=n;i++){

              for(int j=0;j<=m;j++){

                     if(j>=w[i]){

                            if(p[i]+c[i-1][j-w[i]]>c[i-1][j])

                               c[i][j]=p[i]+c[i-1][j-w[i]];

                            else

                            c[i][j]=c[i-1][j];

                     }else

                         c[i][j]=c[i-1][j];

              }

       }

 

【编程题】 数字和为sum的方法数

(动态规划,一个变异的背包问题, 背包必须被装满)

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 

输入例子:
5 15
5 5 10 2 3
 输出例子:
4
方法思想:动态规划思想
代码:

 

1)  java实现

import java.util.Scanner;
 
public class Test {
    public static int n=0;
    public static long calSum(int a[],int sum){
        long dp[][]=new long[n+1][sum+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sum;j++){
                if(j>=a[i])
                    dp[i][j]=dp[i-1][j-a[i]]+dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n][sum];
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            n=in.nextInt();
            int a[]=new int[n+1];
            int sum=in.nextInt();
            for(int i=1;i<=n;i++){
                a[i]=in.nextInt();
            }
            System.out.println(calSum(a,sum));
        }
        in.close();
    }
 
}

 

    2)c++语言实现

#include<iostream>

using namespace std;

 

int w[1001];

long long dp[1001];

 

int main(){

       int n,sum,i;

       while(cin>>n>>sum){

              for(i=1;i<=n;i++)

                 cin>>w[i];

             

              for(i=0;i<=sum;i++){

                     if(i==0)

                        dp[i]=1;

                     else

                        dp[i]=0;

              }

             

              for(i=1;i<=n;i++){

                     for(int j=sum;j>=0;j--){

                            if(j>=w[i]){

                                   dp[j]=dp[j]+dp[j-w[i]];  //dp[j]=不加入第i个物品时重量为dp[j]的方

//式+加入这次第i个物品,那么之前dp[j-w[i]]的放入方式

                                   //cout<<dp[j]<<" ";

                            }

                     }

//cout<<"\n";

              }

              cout<<dp[sum]<<endl;

       }

       return 0;

      

}

或者使用二维数组:

#include<iostream>

#include<vector>

using namespace std;

 

const int MAXN=1005;

long long dp[MAXN][MAXN];

vector<int> ori;

 

int main(){

      

       int N,M;

       cin>>N>>M;

       ori.resize(N+1);

       for(int i=1;i<=N;i++)

          cin>>ori[i];

         

       dp[0][0]=1;

      

       for(int i=1;i<=N;i++){

              for(int j=M;j>=0;j--){

                     if(j>=ori[i]){

                            dp[i][j]=dp[i-1][j-ori[i]] + dp[i-1][j];

                     }else

                         dp[i][j]=dp[i-1][j];

              }

       }

       cout<<dp[N][M]<<endl;

       return 0;

      

}