华师一附中OI组

标题: P1049 装箱问题 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-7-15 09:35
标题: P1049 装箱问题
https://www.luogu.org/problemnew/show/P1049

题目描述
有一个箱子容量为 V （正整数，V≤20000 ），同时有 n 个物品（0<n≤30），每个物品有一个体积（正整数）。

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

输入输出格式
输入格式：
1 个整数，表示箱子容量

1 个整数，表示有 n 个物品

接下来 n 行，分别表示这 n 个物品的各自体积

输出格式：
1 个整数，表示箱子剩余空间。

输入输出样例
输入样例#1：
24
6
8
3
12
7
9
7
输出样例#1：
0
说明
NOIp2001普及组 第4题

作者: 倚窗倾听风吹雨    时间: 2018-7-15 09:35
  1. #include<iostream>
  2. using namespace std;
  3. int v,n,a[50],f[50][20010],ans;
  4. int i,j;
  5. int main()
  6. {
  7.     cin>>v;
  8.     cin>>n;
  9.     for(i=1;i<=n;i++)
  10.         cin>>a[i];
  11.     for(i=1;i<=n;i++)
  12.     {
  13.         for(j=1;j<=v;j++)
  14.         {
  15.             f[i][j]=f[i-1][j];
  16.             if(j-a[i]>=0)
  17.                 if(f[i-1][j-a[i]]+a[i]>f[i][j])
  18.                 f[i][j]=f[i-1][j-a[i]]+a[i];
  19.             ///cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
  20.         }
  21.     }
  22.     ans=v-f[n][v];
  23.     cout<<ans;
  24.     return 0;
  25. }
复制代码
作者: 黄煦喆    时间: 2018-8-29 16:13
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int w[35];
  5. int n,ans,V;
  6. int dp[20005];
  7. int main()
  8. {
  9.     cin>>V>>n;
  10.     for(int i=1;i<=n;i++)cin>>w[i];
  11.     for(int i=1;i<=n;i++)
  12.         for(int j=V;j>=w[i];j--)
  13.             dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
  14.      ans=*max_element(dp+1,dp+V+1);
  15.      cout<<V-ans;
  16.      return 0;
  17. }
复制代码
作者: Scorpio    时间: 2018-10-2 10:12
  1. #include<iostream>
  2. using namespace std;
  3. int a[31],f[21000];
  4. int i,j,v,n;
  5. int main()
  6. {
  7.     cin>>v>>n;
  8.     for(i=1;i<=n;i++)
  9.         cin>>a[i];
  10.     for(i=1;i<=n;i++)
  11.         for(j=v;j>=a[i];j--)
  12.             f[j]=max(f[j-a[i]]+a[i],f[j]);
  13.     cout<<v-f[v];
  14.     return 0;
  15. }
复制代码
作者: admin    时间: 2020-4-6 11:09
用dfs来一波，训练PMN
  1. #include <iostream>
  2. using namespace std;
  3. int ans=999999;
  4. int n,V,a[40],sum;
  5. bool b[40];
  6. void pr()
  7. {
  8.                 if (sum<=V) ans=min(ans,V-sum);
  9. }
  10. void dfs(int i)
  11. {
  12.         if (i>n) pr();
  13.         else
  14.         {
  15.                 b[i]=0;  ///不选 没变化
  16.                 dfs(i+1);
  17.                
  18.                 b[i]=1;///选了  
  19.                 sum+=a[i];///总和加了
  20.                 if (sum<=V) dfs(i+1);
  21.                 sum-=a[i];///退回去
  22.         }
  23. }
  24. int main()
  25. {
  26.         cin>>V>>n;
  27.         for (int i=1; i<=n; i++) cin>>a[i];
  28.         dfs(1);
  29.         cout<<ans;
  30. }
复制代码
作者: admin    时间: 2020-6-13 19:53
背包（DP）思路来一波，简单的DP
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int f[20020][40];
  4. int V,N,a[40];
  5. int main()
  6. {
  7.         int ans=0;
  8.         cin>>V>>N;
  9.         for (int i=1; i<=N; i++) cin>>a[i];
  10.         f[0][0]=1;
  11.         for (int n=1; n<=N; n++)
  12.                 for (int v=0; v<=V; v++)
  13.                         {
  14.                                 int t1=f[v][n-1];///buzhuang
  15.                                 int t2;
  16.                                 if (v>=a[n]) t2=f[v-a[n]][n-1];
  17.                                 else t2=0;/// yaozhuang
  18.                                 f[v][n]=t1||t2;
  19.                         }
  20.         ans=20019;
  21.         while (f[ans][N]==0) ans--;
  22.         cout<<V-ans;
  23.         return 0;
  24. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2