背包型动态规划

2019-08-09

这里是关于背包型动态规划的题目以及程序

背包型动态规划

装箱问题

题目描述 Description

有一个箱子容量为 $V$（正整数，$ 0 \leq V \leq 20000$），同时有$n$个物品（$0 < n \leq 30$），每个物品有一个体积（正整数）。

要求$n$个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述 Input Description

一个整数$v$，表示箱子容量
一个整数$n$，表示有n个物品
接下来$n$个整数，分别表示这$n$ 个物品的各自体积

输出描述 Output Description

一个整数，表示箱子剩余空间。

样例输入 Sample Input

24
6
8
3
12
7
9
7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

无

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<scoreeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

ll a[31], dp[20001]={0};  //容量为0到20001的货车能取的最大体积的货物

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    ll v,n;  
    v=read();
    n=read(); 
    for(int i=0; i<n; i++) 
    {  
        a[i]=read();  
        for(int j=v; j>=a[i]; j--)//容积从a[i]到v的货车都可以选择取或不取第i个货，每个货车都进行一次判断
              dp[j]//目前决策下容积为j的火车能取的最多的货
                = max(dp[j]//目前决策下容积为j的火车在选择取a[i]前，能取的最多的货
                            , dp[j-a[i]]+a[i]);//容积为j-a[i]的货车能取的最多的货+a[i]的货占用的体积 
      //这种方法可以保证每次得到的最大体积都不超过容积j
     }
     
   printf("%d\n",v-dp[v]);//剩余体积为v能取的最大体积的货 
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

乌龟棋

题目描述 Description

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子。$1 \; 2 \; 3 …… N-1 \; N$ ，每个格子上一个分数（非负整数）。棋盘第$1$格是唯一的起点，第$N$格是终点。

游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中$M$张爬行卡片，分成$4$种不同的类型（$M$张卡片中不一定包含所有$4$种类型的卡片，见样例），每种类型的卡片上分别标有$1、2、3、4$四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入描述 Input Description

输入的每行中两个数之间用一个空格隔开。第$1$行$2$个正整数$N$和$M$，分别表示棋盘格子数和爬行卡片数。第$2$行$N$个非负整数，$a_1 \; a_2 \; …… \; a_N$，其中$a_i$表示棋盘第$i$个格子上的分数。第$3$行$M$个整数，$b_1 \; b_2 \; …… \; b_M $，表示$M$张爬行卡片上的数字。输入数据保证到达终点时刚好用光$M$张爬行卡片，即$ N - 1 = \sum_{i=1}^{M} b_i$

输出描述 Output Description

输出一行一个整数

样例输入 Sample Input

13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1

样例输入 Sample Input

455

数据范围及提示 Data Size & Hint

对于$30%$的数据有$1 \leq N \leq 30，1 \leq M \leq 12$。

对于$50%$的数据有$1 \leq N \leq 120，1 \leq M \leq 50$，且 $4$ 种爬行卡片，每种卡片的张数不会超过$20$。

对于$100%$的数据有$1 \leq N \leq 350，1 \leq M \leq 120$，且 $4$ 种爬行卡片，每种卡片的张数不会超过$40$；

$0 \leq ai \leq 100，1 \leq i \leq N，1 \leq bi \leq 4，1 \leq i \leq M$。输入数据保证$ N - 1 = \sum_{i=1}^{M} b_i$

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<scoreeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
const int maxn=350+10;

int a[maxn],d[45][45][45][45],b[5];

inline long long read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    int n,m;
    n=read();
    m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++)
    {
        int p;
        p=read();
        b[p]++;
    }
    d[0][0][0][0]=a[1];
    for(int i=0;i<=b[1];i++)
     for(int j=0;j<=b[2];j++)
      for(int k=0;k<=b[3];k++)
       for(int l=0;l<=b[4];l++)
       {
        int score=a[1+i+2*j+3*k+4*l];
        if(i) d[i][j][k][l]=max(d[i][j][k][l],d[i-1][j][k][l]+score);
        if(j) d[i][j][k][l]=max(d[i][j][k][l],d[i][j-1][k][l]+score);
        if(k) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k-1][l]+score);
        if(l) d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k][l-1]+score);
       }
    printf("%d\n",d[b[1]][b[2]][b[3]][b[4]]);
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}