题解

239 条题解

  • 6
    @ 2017-05-08 09:04:13
    /*
    又是一个裸的0/1Orz
    要使剩余体积最小
    就是要尽量装满
    然后总体积减去装掉的体积
    QAQ
    */
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int a[40];
    int V,n;
    int f[20010];
    
    int main()
    {
        cin>>V>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            for(int j=V;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+a[i]);
        cout<<V-f[V];
        return 0;
    }
    
  • 3
    @ 2017-10-27 19:43:28
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    int a[33];
    int f[33][20010];
    int main()
    {
        //freopen("box.in","r",stdin);
        //freopen("box.out","w",stdout);
        int v,n;
        cin>>v>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=v;j++)
            {
                if(j>=a[i])
                f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
                else
                f[i][j]=f[i-1][j];
            }
        cout<<v-f[n][v]<<endl;
        return 0;
    }
    
  • 2
    @ 2017-11-22 18:21:29

    弱化版的01背包
    水过...

    #include<bits/stdc++.h>
    using namespace std;
    int a[31],f[20001];
    int main(){
        int n,m;
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            for(int j=m;j>=a[i];j--)
                f[j]=max(f[j],f[j-a[i]]+a[i]);
        printf("%d",m-f[m]);
        return 0;
    }
    
  • 2
    @ 2017-11-01 16:59:22

    第二道DP题(。・д・。)

    #include<iostream>
    using namespace std;
    int a[35];
    int f[35][20005];
    int main()
    {
        int v,n;
        cin>>v>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=v;j++)
        {
            if(j>=a[i])
            f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
            else
            f[i][j]=f[i-1][j];
        }
        cout<<v-f[n][v]<<endl;
        return 0;
    }
    
    
  • 1
    @ 2021-02-04 16:17:00

    #include<bits/stdc++.h>
    using namespace std;

    int dp[20001][20001],v,n,a[31];

    int main()
    {
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=v;j++)
    {
    dp[i][j]=dp[i-1][j];
    if(a[i]<=j)
    {
    if(dp[i-1][j-a[i]]+a[i]>dp[i][j])
    {
    dp[i][j]=dp[i-1][j-a[i]]+a[i];
    }
    }
    }
    }
    cout<<v-dp[n][v];
    return 0;
    }

  • 1
    @ 2016-05-07 19:08:01

    那么多dp,我来发个搜索吧
    普通的暴搜显然要炸,但本题中途相遇搜索可以通过。最大数据31ms
    O(1.414^n * logn)
    ```c++
    // ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //

    #include <cstdio>
    #include<set>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;

    int v;
    int t[30];
    int n;
    int k1, k2;
    bool sel[30];
    set<int> s;
    void dfs1(int lim)
    {
    if (lim == k1)
    {
    int sum = 0;
    for (int i = 0;i<k1;i++)
    {
    if (sel[i])sum += t[i];
    }
    if (sum == v)
    {
    putchar('0');
    exit(0);
    }
    if (sum<v)
    {
    s.insert(sum);
    }
    }
    else
    {
    sel[lim] = true;dfs1(lim + 1);
    sel[lim] = false;dfs1(lim + 1);
    }
    }
    int ans;
    void dfs2(int lim)
    {
    if (lim == n)
    {
    int sum = 0;
    for (int i = k1;i<n;i++)
    if (sel[i])sum += t[i];
    int maxm = v - sum;
    if (maxm < 0)return;
    if (s.count(maxm))
    {
    putchar('0');
    exit(0);
    }
    set<int>::iterator i = s.insert(maxm).first;
    if (i == s.begin())ans = min(ans, maxm);
    else
    {
    i--;
    int addup = *i;
    ans = min(ans, maxm - addup);
    i++;
    s.erase(i);
    }
    }
    else
    {
    sel[lim] = true;dfs2(lim + 1);
    sel[lim] = false;dfs2(lim + 1);
    }
    }
    int main()
    {
    scanf("%d%d", &v, &n);
    for (int i = 0;i<n;i++)scanf("%d", t + i);
    ans = v;
    k1 = n / 2;
    k2 = n - k1;
    dfs1(0);
    dfs2(k1);
    printf("%d", ans);
    }
    ```

  • 1
    @ 2015-12-13 15:51:38

    写了这么久DP,发个最简的代码吧,这上面我不知道如何在include前面加#号,你们记得加上
    include<iostream>
    include<algorithm>
    using namespace std;
    int v, n;
    int w[200001];
    int dp[200001];
    int main(){
    cin >> v >> n;
    for (int i = 0; i < n; i++)
    {
    cin >> w[i];
    }
    for (int i = 0; i < n; i++)
    {
    for (int j = v; j >= w[i]; j--){
    dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
    }
    }
    cout << v - dp[v];
    return 0;
    }

  • 0
    @ 2020-08-29 11:08:26

    #include <iostream>
    using namespace std;
    int a[40],f[20010];
    int V,n;
    int main()
    {
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    for(int j=V;j>=a[i];j--)
    f[j]=max(f[j],f[j-a[i]]+a[i]);
    cout<<V-f[V]<<endl;
    return 0;
    }

  • 0
    @ 2020-08-29 10:54:34

    #include<bits/stdc++.h>
    using namespace std;
    int v,n,f[20001],a[20001];
    int main()
    {
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];

    for(int i=1;i<=n;i++)
    for(int j=v;j>=1;j--)
    if(j>=a[i])
    f[j]=max(f[j],f[j-a[i]]+a[i]);
    cout<<v-f[v]<<endl;
    return 0;
    }

  • 0
    @ 2020-08-29 10:43:38

    #include<iostream>
    using namespace std;
    int a[40];
    int V,n;
    int f[20010];

    int main()
    {
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    for(int j=V;j>=a[i];j--)
    f[j]=max(f[j],f[j-a[i]]+a[i]);
    cout<<V-f[V];
    return 0;
    }

  • 0
    @ 2020-07-26 22:13:56

    01背包的变式

    #include<bits/stdc++.h>
    using namespace std;
    int n,v,a[35];
    bool dp[20005];
    int main(){
        cin>>v>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        dp[0]=1;
        for(int i=1;i<=n;i++)
        for(int j=v;j>=a[i];j--)
            if(dp[j-a[i]])dp[j]=1;
        int maxx=0;
        for(int i=v;i>=1;i--)
            if(dp[i]){
                maxx=i;
                break;
            }
        cout<<v-maxx;
        return 0;
    }
    
  • 0
    @ 2020-05-15 22:36:32

    这道题看似是搜索,但是可以用背包做。

    题目要求求出最小的剩余空间,也就是要求出最大的可装重量

    这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的01背包问题:

    有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)和一个价值(等于体积)。

    要求n个物品中,任取若干个装入箱内,使总价值最大。

    对于每一个物体,都有两种状态:装 与不装

    那么,对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )(w为重量(即价值))

    其中,f ( m - w[i] ) 指在装了物品i后,箱子的剩余容量能装的最大重量

    f ( m - w[i] ) + w[i] 指在在装了物品i后,箱子能装的最大重量

    程序如下:

    #include<cstdio>
    using namespace std;
    int m,n;                m即箱子容量V
    int f[20010];
    int w[40];
    int main(){
        int i,j;
        scanf("%d%d",&m,&n);
        for(i=1;i<=n;i++){
            scanf("%d",&w[i]);
        }
        for(i=1;i<=n;i++){
            for(j=m;j>=w[i];j--){                            注意:这里必须是从m到w[i],否则一个物体会被多次装入箱子,见例1
                if(f[j]<f[j-w[i]]+w[i]){
                    f[j]=f[j-w[i]]+w[i];
                }
            }
        }
        printf("%d\n",m-f[m]);
    }
    

    例1: 输入:

    5 1 1 假如在遍历容量m时从小到大遍历,你会发现:

    f (2) = f (2 - 1) + w[1] = f (1) +w[1] = 2
    f (3) = ... = 3
    f (4) = 4
    f (5) = 5
    最后的答案就是5-5=0,然而正解是5-1=4

  • 0
    @ 2020-04-08 15:31:40
    #include <iostream>         //[2001普及组-D]装箱问题
    #include <algorithm>        //01背包问题
    using namespace std;
    const int MAXW = 20002;
    
    int main()
    {
        int V, n, W[31];
        int dp[MAXW] = {0};
        cin >> V >> n;
        for (int i = 1; i <= n; i++)
            cin >> W[i];
    
        for (int i = 0; i <= n; i++)
            for (int j = V; j >= W[i]; j--)
                dp[j] = max(dp[j], dp[j - W[i]] + W[i]);
    
    
        cout << V - dp[V] << endl;
    
        return 0;
    }
    //前i个物品,
    //dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + w[i]);
    
    
  • 0
    @ 2019-10-06 21:23:44

    /*01背包的变式,费用=价值。*/
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int dp[100005],a[100005],v,n,i,j;
    int main()

    {
    scanf("%d%d",&v,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    for(j=v;j>=a[i];j--)
    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    printf("%d\n",v-dp[v]);
    return 0;
    }

  • 0
    @ 2019-10-06 21:22:25

    //01背包的变式,费用=价值。
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int dp[100005],a[100005],v,n,i,j;
    int main()

    {
    scanf("%d%d",&v,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    for(j=v;j>=a[i];j--)
    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    printf("%d\n",v-dp[v]);
    return 0;
    }

  • 0
    @ 2019-10-06 21:20:57

    //01背包的变式,费用=价值
    AC代码:
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int dp[100005],a[100005],v,n,i,j;
    int main()

    {
    scanf("%d%d",&v,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    for(j=v;j>=a[i];j--)
    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
    printf("%d\n",v-dp[v]);
    return 0;
    }

  • 0
    @ 2018-11-04 14:14:00

    c++代码
    #include<bits/stdc++.h>
    using namespace std;
    int a[33];
    bool f[33][20003];
    int main(){
    int v,n;
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=v;j++){
    f[i][j]=f[i-1][j];
    if(j>=a[i]) f[i][j]=f[i][j] || f[i-1][j-a[i]];
    }
    for(int i=v;i>=0;i--)
    if(f[n][i]){
    printf("%d",v-i);
    return 0;
    }
    }

  • 0
    @ 2018-09-24 22:52:16

    //(悄咪咪)这是个80分炒鸡水的做法,证明数据之水~

    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int a[31];
    int ans[1000];
    int main()
    {
    int v,n,v1=0;
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+1+31);
    for(int i=31;i>=1;)
    {
    if(a[i]<=v-v1)
    {
    v1+=a[i];
    i--;
    }
    else if(a[i]>v-v1)
    {
    i--;
    }

    }
    cout<<v-v1;
    return 0;
    }

  • 0
    @ 2016-05-24 18:14:59

    普通背包问题加一个限制条件:
    最优解不大于最大容量
    大于则维持原样,不大于则按普通背包问题
    ```c++
    #include <cstdio>
    #include <iostream>

    using std::max;

    int main(void){
    freopen("in.txt","r",stdin);
    int n,maxv;
    int v[500];
    int f[50000]={0};
    scanf("%d%d",&maxv,&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&v[i]);

    for(int i=1;i<=n;i++)
    for(int j=maxv;j>=v[i];j--)
    f[j]=f[j-v[i]]+v[i]>maxv?f[j]:max(f[j-v[i]]+v[i],f[j]);
    printf("%d",maxv-f[maxv]);
    return 0;
    }
    ```

    • @ 2016-10-18 18:40:38

      就是普通的背包问题,最优解不大于最大容量也是存在于普通的背包问题的

    • @ 2019-09-28 14:25:59

      应该写cpp而不是c++,
      这样才能高亮显示。

  • 0
    @ 2015-12-14 19:00:04

    #include <iostream>
    #include <math.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    const int N = 1005;
    int v,n,f[N][N],w[N],ans = 0;
    int main(){
    scanf("%d%d",&v,&n);
    for(int i = 1;i <= n;i ++){
    scanf("%d",&w[i]);
    }
    for(int i = 1;i <= n;i ++){
    for(int j = v;j >= 0;j --){
    f[i][j] = j >= w[i] ? max(f[i - 1][j - w[i]] + w[i],f[i - 1][j]) : f[i - 1][j];
    }
    }
    ans = v - f[n][v];
    printf("%d",ans);
    return 0;
    }

    • @ 2016-11-03 10:40:55

      就喜欢不用优化的 boy

信息

ID
1133
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
10690
已通过
4435
通过率
41%
被复制
16
上传者