题解

239 条题解

  • 0
    @ 2015-11-04 18:20:44

    VAR box:array[1..30] of integer;
    h:array[0..20000] of boolean;
    k,v,n,i:integer;

    begin
    fillchar(h,sizeof(h),false);
    readln(v);
    readln(n);
    for i:=1 to n do
    readln(box[i]);
    h[0]:=true;
    for i:=1 to n do
    for k:=v downto box[i] do
    begin
    h[k]:=h[k] or h[k-box[i]];
    if h[n] then begin writeln(0); halt; end;
    end;
    for i:=v downto 0 do if h[i] then break;
    writeln(v-i);
    end.
    为什么不对。。

  • 0
    @ 2015-10-22 14:51:31

    #include <cstdio>
    #include <cstring>

    using namespace std;

    inline int max(int a,int b) {
    return a>b?a:b;
    }

    int main(void) {
    int v=0,n=0;
    scanf("%d %d",&v,&n);
    int c[n];
    for (int i=0;i<n;++i)
    scanf("%d",c+i);
    int f[v+1];
    memset(f,0,(v+1)*sizeof(int));
    for (int i=0;i<n;++i)
    for (int j=v;j>=0;--j)
    if (j>=c[i])
    f[j]=max(f[j],f[j-c[i]]+c[i]);
    int ans=9999999;
    for (int i=0;i<=v;++i)
    if (v-f[i]<ans)
    ans=v-f[i];
    printf("%d\n",ans);
    return 0;
    }
    QwQ我好菜

  • 0
    @ 2015-08-24 16:19:54

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int N = 20010;
    const int M = 10;
    LL dp[N];
    int v,n,a,MAX;
    vector<int>V;
    void add(int x)
    {
    int k = V.size();
    for(int i = 0; i < k; i++)
    if(V[i] + x <= v &&!dp[V[i] + x]) //优先没弄好,RE,orz
    {
    dp[V[i] + x] = 1;
    MAX = max(MAX,V[i] + x);
    V.push_back(V[i] + x);
    }
    }
    int main()
    {
    while(~scanf("%d%d",&v,&n))
    {
    memset(dp,0,sizeof(dp));
    V.clear();
    V.push_back(0);
    dp[0] = 1;
    MAX = 0;
    for(int i = 0; i < n; i++)
    {
    scanf("%d",&a);
    if(MAX != v)
    add(a);
    }
    printf("%d\n",v - MAX);
    }
    }

  • 0
    @ 2015-08-20 15:41:04

    #include<stdio.h>
    #include<string.h>

    int dp[50][20020],v,n,w[50];

    int f(int t,int v)
    {
    if(t==n) return 0;
    if(dp[t][v]>=0) return dp[t][v];
    dp[t][v]=f(t+1,v);
    if(v>=w[t])
    {
    int temp=f(t+1,v-w[t])+w[t];
    if(temp>dp[t][v]) dp[t][v]=temp;
    }
    return dp[t][v];
    }

    int main()
    {
    scanf("%d%d",&v,&n);
    for(int i=0;i<n;i++)
    scanf("%d",&w[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",v-f(0,v));
    return 0;
    }
    记忆化搜索 0-1背包,只是物品体积和价值相同

  • 0
    @ 2015-08-17 10:57:50

    。。。。。数组开小了,我的AC率呀 %>_<%

  • 0
    @ 2015-08-15 13:27:38

    刚学动态规划就自己做出来了,我真是屌到没朋友~( ̄▽ ̄~)~
    设d(i,j)表示把前i个物体装到容量为j的箱子中的最大体积
    则状态转移方程为d(i,j)=max{d(i-1,j),d(i-1,j-v[i])+v[i] |j>=v[i]}

    int main() {
    memset(d,0,sizeof(d));
    cin>>V>>n;
    //for (int i=1;i<=n;++i) cin>>v[i];
    for (int i=1;i<=n;++i) {
    cin>>v;
    for (int j=0;j<=V;++j) {
    d[i][j]=d[i-1][j];
    if (j>=v)
    d[i][j]=max(d[i][j],d[i-1][j-v]+v);
    //printf("d(%d,%d)=%d\n",i,j,d[i][j]);
    }
    }
    cout<<V-d[n][V];
    return 0;
    }

  • 0
    @ 2015-06-25 08:50:36

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,v[50],V,f[20001];
    int main()
    {
    scanf("%d%d",&V,&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    f[j]=max(f[j],f[j-v[i]]+v[i]);
    printf("%d",V-f[V]);
    }

  • 0
    @ 2015-05-31 08:23:23

    program xiangzi;
    var
    a,b:array[1..20000] of longint;
    i,j,k,l,m,n,v:longint;
    begin
    readln(v);
    readln(n);
    for i:=1 to n do
    readln(a[i]);
    for i:=1 to n do
    for j:=v downto a[i] do
    if b[j-a[i]]+a[i]>b[j]
    then b[j]:=b[j-a[i]]+a[i];
    writeln(v-b[v]);
    end.

  • 0
    @ 2015-05-13 17:48:32

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 332 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 332 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 332 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 332 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 332 KiB, score = 10
    Accepted, time = 15 ms, mem = 332 KiB, score = 50
    代码
    #include <iostream>
    #define MIN(A,B) A<B?A:B

    using namespace std;

    int main(){
    int capacity;
    int itemNum;
    int last[20001];
    int itemCap[31];
    cin >> capacity >> itemNum;
    for(int i = 1; i <= itemNum; i++)
    cin >> itemCap[i];
    for(int i = 0; i <= capacity; i++)
    last[i] = i;
    for(int i = 1; i <= itemNum; i++){
    for(int j = capacity; j >= 1; j--){
    if(j >= itemCap[i]) last[j] = MIN(last[j], last[j-itemCap[i]]);
    }
    }
    cout << last[capacity] << endl;
    }

  • 0
    @ 2015-03-18 10:55:04

    #include<stdio.h>//使得被装入的箱子体积最大
    int dp[31][20001],v[31],w[31];
    int max(int a,int b)
    {
    if(a>b)return a;
    else return b;
    }
    int main()
    {
    int i,j,vol,n;
    scanf("%d%d",&vol,&n);
    for(i=0;i<n;i++)
    {
    scanf("%d",&v[i]);
    w[i]=v[i];
    }
    for(i=n-1;i>=0;i--)
    {
    for(j=0;j<=vol;j++)
    {
    dp[i][j]=(i==n-1?0:dp[i+1][j]);
    if(j>=v[i])dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);
    }
    }
    printf("%d",vol-dp[0][vol]);
    return 0;
    }
    0-1背包的改编,将原来求的重量最大值改成体积最大就行了

  • 0
    @ 2015-01-24 17:08:21

    01背包
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int V;
    int N;
    int a[200000];
    int f[200000];
    int max1(int x,int y)
    {
    if(x>y) return x;
    else return y;
    }
    int main()
    {
    scanf("%d",&V);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
    scanf("%d",&a[i]);
    }

    for(int i=1;i<=N;i++)
    for(int v=V;v>0;v--)
    {
    if(a[i]<=v)
    {
    f[v]=max1(f[v],f[v-a[i]]+a[i]);
    }
    else
    f[v]=f[v];
    }
    cout<<V-f[V];
    return 0;
    }

  • 0
    @ 2015-01-14 17:32:29

    这就是我突然想到的思路,既然AC了,说明是没问题的。

    当我用楼下的办法做这题,发现它每次枚举都是true的值,就是之前有的状态,中间都浪费掉了时间,大约40W次循环(拿20个物品的情况)但是我这个程序的思路是把每次的状态放入一个队列V中,lenv记录长度,每次只要枚举队列里的状态,PD判断该状态是否已经在队列里面了。

    这样的话考虑最坏情况,也只要枚举1+2+3+....+19+20次循环因此我开了个300的V数组。

    不知道这也算不算是动规。总之看大家题解好像还没有这个思路,发上来可以大家看看。另外谁能告诉下,是不是一道动态规划的题,有时候是不是动态规划的方法有很多种的啊???我看这些动规好像都写的各种各样的?还是说只有某一种算?

    ###block code
    program P1133;
    var v:array[1..300] of longint; //队列存储状态
    pd:array[0..200000] of boolean; //是否存在该状态的背包
    n,i,w,m,j,max,lenv:longint;
    begin
    read(n); read(m); fillchar(v,sizeof(v),0); max:=0; fillchar(pd,sizeof(pd),false);
    pd[0]:=true;
    lenv:=1;
    for i:=1 to m do //干嘛要读入?直接拿来算
    begin
    read(w); //物品体积
    for j:=1 to lenv do
    if (v[j]+w<=n) and (pd[v[j]+w]=false) then //如果不超过背包总大小,同时不存在该状态
    begin
    inc(lenv); v[lenv]:=v[j]+w; pd[v[j]+w]:=true; //加入队列,判断是不是当前最大值
    if v[j]+w>max then
    max:=v[j]+w;
    end;
    end;

    write(n-max); //答案
    end.

    • @ 2015-02-02 17:36:08

      uses math;
      var
      v1,n,k:longint;
      v:array[1..100] of longint;
      cc:array[1..30,1..20000] of longint;
      flag:array[1..30,1..20000] of boolean;
      function bb(i,j:longint):longint;
      begin
      if flag[i,j] then exit(cc[i,j]);
      if i=1 then if j>=v[i] then begin cc[i,j]:=v[i];flag[i,j]:=true;exit(v[i]);end
      else begin cc[i,j]:=0;flag[i,j]:=true;exit(0);end;
      if j<v[i] then begin cc[i,j]:=bb(i-1,j);flag[i,j]:=true;exit(cc[i,j]);end;
      bb:=max(bb(i-1,j-v[i])+v[i],bb(i-1,j));
      cc[i,j]:=bb;
      flag[i,j]:=true;
      end;
      begin
      readln(v1);
      readln(n);
      fillchar(flag,sizeof(flag),0);
      for k:=1 to n do readln(v[k]);
      writeln(v1-bb(n,v1));
      end.

  • 0
    @ 2015-01-14 17:11:20

    请问这是动态规划么?我在自学= =前几星期都搞不懂。现在稍微懂了,虽然AC了不过求大家看看是不是动态规划。
    枚举了好多啊- -粗略算了下有40W次循环,不过DPS貌似有100W次循环- -

    写完后对此题萌生了一个新的想法,不知道也算不算是动态规划,它能把时间复杂度降低到只要循环约1 2百次。希望大家看看,是楼上。

    ###block code
    program P1133;
    var v:array[0..20000] of boolean; //记录是否有这种情况
    n,i,w,m,j,max:longint;
    begin
    read(n); read(m); fillchar(v,sizeof(v),false); max:=0;
    v[0]:=true;
    for i:=1 to m do //不存物品重量直接读入计算
    begin
    read(w);
    for j:=n-w downto 0 do //枚举的好厉害,怕怕
    if v[j]=true then
    begin
    v[j+w]:=true;
    if j+w>max then //找最大的情况
    max:=j+w;
    end;
    end;

    write(n-max); //剩余的背包数目输出
    end.

  • 0
    @ 2014-12-03 16:38:50

    program _1133zhuangxiang;
    var n0,v0,i,j:longint;
    Volume:array[1..100]of longint;
    f:array[0..20000]of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
    begin
    fillchar(f,sizeof(f),0);
    for i:=1 to n0 do
    for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量(加上第i个物品)
    if Volume[i]<=j then// 只有还有空间时才重新计算最大值
    f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
    exit(f[v0]);
    end;

    begin
    read(v0,n0);
    for i:=1 to n0 do
    read(Volume[i]);
    writeln(v0-DP(n0,v0));
    end.
    program _1133zhuangxiang;
    var n0,v0,i,j:longint;
    Volume:array[1..100]of longint;
    f:array[0..20000]of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
    begin
    fillchar(f,sizeof(f),0);
    for i:=1 to n0 do
    for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量(加上第i个物品)
    if Volume[i]<=j then// 只有还有空间时才重新计算最大值
    f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
    exit(f[v0]);
    end;

    begin
    read(v0,n0);
    for i:=1 to n0 do
    read(Volume[i]);
    writeln(v0-DP(n0,v0));
    end.
    program _1133zhuangxiang;
    var n0,v0,i,j:longint;
    Volume:array[1..100]of longint;
    f:array[0..20000]of longint;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;

    function DP(n0,v0:longint):longint;// f数组为容量为v时的最大价值
    begin
    fillchar(f,sizeof(f),0);
    for i:=1 to n0 do
    for j:=v0 downto 0 do// 重新计算容量为j时的最大装箱量(加上第i个物品)
    if Volume[i]<=j then// 只有还有空间时才重新计算最大值
    f[j]:=max(f[j],f[j-Volume[i]]+Volume[i]);// 容量为j时 选上第i个物品总空间更大还是不选更大
    exit(f[v0]);
    end;

    begin
    read(v0,n0);
    for i:=1 to n0 do
    read(Volume[i]);
    writeln(v0-DP(n0,v0));
    end.

  • 0
    @ 2014-10-30 19:48:49

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 281 ms, mem = 391952 KiB, score = 10
    测试数据 #1: Accepted, time = 281 ms, mem = 391952 KiB, score = 10
    测试数据 #2: Accepted, time = 281 ms, mem = 391956 KiB, score = 10
    测试数据 #3: Accepted, time = 234 ms, mem = 391948 KiB, score = 10
    测试数据 #4: Accepted, time = 265 ms, mem = 391948 KiB, score = 10
    Accepted, time = 1342 ms, mem = 391956 KiB, score = 50
    代码
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define M 10000
    using namespace std;

    int dp[M][M],i,j,V,n,w[M];

    int main() {
    // freopen("pack.in","r",stdin);
    // freopen("pack.out","w",stdout);
    memset(dp,0,sizeof(dp));
    memset(w,0,sizeof(w));
    scanf("%d", &V);
    scanf("%d", &n);
    for(i = 1; i <= n; i++) scanf("%d",&w[i]);
    for(i = 1; i <= n; i++) {
    for(j = V; j > 0; j--) {
    if(j >= w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + w[i]);
    else dp[i][j] = dp[i-1][j];
    }
    }
    printf("%d",V - dp[n][V]);
    }

  • 0
    @ 2014-10-22 19:10:08

    var
    v,n,i,j,t:integer;
    w:array[1..30] of integer;
    f:array[0..20000] of boolean;
    begin
    readln(v);readln(n);
    for i:=1 to n do
    readln(w[i]);
    f[0]:=true;
    for i:=1 to n do
    for j:=v downto w[i] do//不能使用for j:=w[i] to v do
    if f[j-w[i]] then f[j]:=true;
    t:=v;
    while not f[t] do
    dec(t);
    writeln(v-t);
    end.

  • 0
    @ 2014-09-24 23:15:30

    program ex1;

    var
    s: array[0..20000] of 0..1;
    sv, v, n, i, j: integer;
    begin
    readln(sv);
    readln(n);
    s[0] := 1;
    for i := 1 to n do
    begin
    readln(v);
    for j := sv - v downto 0 do
    if s[j] = 1 then
    s[j + v] := 1;
    end;
    for i := sv downto 0 do
    if s[i] = 1 then
    begin
    writeln(sv - i);
    exit;
    end;
    end.

  • 0
    @ 2014-08-17 09:51:29

    #include<iostream>
    using namespace std;
    int N,v,n[1000],f[1000000],i,j;
    main()
    {
    cin>>v>>N;
    for(i=1;i<=N;i++)
    cin>>n[i];
    for(i=1;i<=N;i++)
    for(j=v;j>=n[i];j--)
    f[j]=max(f[j],f[j-n[i]]+n[i]);
    cout<<v-f[v];
    }

  • 0
    @ 2014-07-14 14:47:56

    #include<cstdio>
    #define IOFileName "P1133"
    const int maxV=20002;
    int V,v,n,ans;
    bool box[maxV]={true};
    int main(){
    //freopen(IOFileName".in","r",stdin);
    //freopen(IOFileName".out","w",stdout);
    scanf("%d\n%d\n",&V,&n);
    for(int i=0;i<n;i++){
    scanf("%d\n",&v);
    for(int j=V;j>=0;j--){
    if(box[j]&&j+v<=V){
    box[j+v]=true;
    }
    }
    }
    for(ans=V;!box[ans];ans--);
    printf("%d\n",V-ans);
    }
    260KB+0MS

  • 0
    @ 2014-03-22 10:25:41

    注意输入数据的筛选:
    #include <stdio.h>

    int knapsack01[20001];

    int main(){
    int v;//0 = = 20000
    int n;//0 = = 30
    int vi[31];
    int tempvi;//fliter those vi which > v & if vi == v then print 0
    bool flag;//to print 0
    int i,j;//for loop

    while( ~scanf("%d%d",&v,&n) ){
    flag = 0;

    //input
    for(i=1; i<=n; i++){
    scanf("%d",&tempvi);
    if(tempvi < v)
    vi[i] = tempvi;
    else if(tempvi > v){
    n--;
    i--;
    }else{//tempvi == v
    flag = 1;
    break;
    }
    }

    //special judge when n == 0
    if(n == 0){
    printf("%d\n",v);
    continue;
    }

    //special judge when v == 0
    if(v == 0){
    printf("0\n");
    continue;
    }

    //special judge when haveing vi == v
    if(flag){
    printf("0\n");
    continue;
    }

    //knapsack01 init
    knapsack01[0] = 0;
    for(i=1;i<=v;i++)
    knapsack01[i] = -1000000;//20000 * 30 - 1000000 < 0

    //knapsack01 start
    for(i=1; i<=n; i++)
    for(j=v; j>=vi[i]; j--)
    knapsack01[j] = knapsack01[j] > knapsack01[j - vi[i]] + vi[i] ? knapsack01[j] : knapsack01[j - vi[i]] + vi[i];

    //search for the biggest v which saves the positive number
    for(i=v; i>=0; i--)
    if(knapsack01[i] >= 0)
    break;

    printf("%d\n",v-i);
    }

    return 0;
    }

信息

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