背包问题

简单01背包

有一个箱子容量为v(正整数，0<=v<=2000),同时有n个物品（0<n<=30),每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间最小
输入描述：一个整数v,表示箱子容量；一个整数n,表示有n个物品；接下来n个整数，分别表示这n个物品的各自体积
输出描述：一个整数，表示箱子的剩余空间
样例输入：

24 6   
8 3 12 7 9 7

样例输出：

0

分析：
第一步:确定状态，用dp[i][j]表示前i个物品在容量为j的背包里可以装下的最大体积
第二步：确定状态转移方程：枚举最后一次决策--第i个物品放还是不放；
放： dp[i][j] = dp[i-1][j-v[i]]+v[i];
不放：dp[i][j] = dp[i-1][j];

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int v;//输入体积
    int n;//输入物品个数
    while(cin>>v>>n)
    {
        int Item[30];//保存物品体积
        for(int i=1;i<=n;i++)
            cin>>Item[i];
        int dp[31][2001]={0};//前i个物体放入容量为j的背包总所能占用的最大体积
        for(int i=1;i<=n;i++)
            for(int j=1;j<=v;j++)
            {
                if(Item[i]>j){
                    dp[i][j] = dp[i-1][j]; //如果第i个物体容量比背包大，则不放
                }
                else{
                    dp[i][j] =max(dp[i-1][j],dp[i-1][j-Item[i]]+Item[i]); //状态转移方程
                }
            }
        cout<<dp[n][v]<<endl;
    }
}

价值背包

有N件物品和一个容量为V的背包。第i件物品的容量是c[i],价值是w[i],求解将哪些物体装入背包可使价值总和最大。

这里注意：要分情况恰装满或者小于等于背包容量（初始化不同）
第二种情况

#include<iostream>
#include<cstring>
using namespace std;
const int MaxN =105;
const int MaxM=105;

int main()
{
    int N;//行李箱的最大容量
    int M;//物体的个数
    int c[MaxM];//容量
    int v[MaxM];
    int dp[MaxN][MaxM];
    while(cin>>N>>M)
    {
        for(int i=1;i<=M;i++)
        {
            cin>>c[i];
        }

        for(int i=1;i<=M;i++)
        {
            cin>>v[i];
        }
        for(int i=0;i<=M;i++)
        {
            dp[i][0]=0;
        }
         for(int j=0;j<=N;j++)
        {
            dp[0][j] =0;
        }

        for(int i=1;i<=M;i++)
            for(int j=1;j<=N;j++)
            {
                if(c[i]>j) dp[i][j]=dp[i-1][j];
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);
                }
            }
        cout<<dp[M][N];
    }
}

完全背包

将状态方程改下即可

#include<iostream>
#include<cstring>
using namespace std;
const int MaxN =105;
const int MaxM=105;

int main()
{
    int N;//行李箱的最大容量
    int M;//物体的个数
    int c[MaxM];//容量
    int v[MaxM];
    int dp[MaxN][MaxM];
    while(cin>>N>>M)
    {
        for(int i=1;i<=M;i++)
        {
            cin>>c[i];
        }

        for(int i=1;i<=M;i++)
        {
            cin>>v[i];
        }
        for(int i=0;i<=M;i++)
        {
            dp[i][0]=0;
        }
         for(int j=0;j<=N;j++)
        {
            dp[0][j] =0;
        }

        for(int i=1;i<=M;i++)
            for(int j=1;j<=N;j++)
            {
                if(c[i]>j) dp[i][j]=dp[i-1][j];
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
                }
            }

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

问题待解决

恰好装满的情况未能弄清楚