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题

倚窗倾听风吹雨

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. }
    

复制代码

黄煦喆

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

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

用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

背包（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. }

复制代码