4 条题解

  • 0
    @ 2023-8-20 14:34:35
    #include<bits/stdc++.h>
    using namespace std;
    int w[100001],v[100001],dp[100001];
    int main(){
        int n,m;
        cin>>m>>n;    for(int i=1;i<=n;i++){
            cin>>w[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=m;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
            }
        }
        cout<<m-dp[m];
        return 0;
    }
    
    • 0
      @ 2023-5-26 21:51:39
      /*****************
      备注:
      *****************/
      #include <iostream>
      #include <iomanip>
      #include <cmath>
      #include <cstring>
      #include <algorithm>
      #include <cstdio>
      using namespace std;
      #define LL long long
      #define MAXM 3010
      #define MAXN 3010
      const int N =1e5+10;
      const int INF =0x3f3f3f3f;
      int maxx = -INF,n,minn = INF,v;
      int a[N];
      void dfs(int step,int sum)
      {
      	if (sum <= v) maxx = max(maxx,sum);
      	if (sum > v or step > n) return;
      	dfs(step+1,sum+a[step]);
      	dfs(step+1,sum);
      }
      int main(){
      	cin >> v >> n;
      	for (int i = 1;i<=n;i++)
      	{
      		cin >> a[i];
      	}
      	dfs(1,0);
      	cout << v - maxx;
      	return 0;
      }
      
      
      • 0
        @ 2022-10-26 22:37:13

        #include<bits/stdc++.h> using namespace std; int q,a[100001],b[100001]; int main(){ int w; cin>>w>>q; int i, j; for (i = 0; i < q; i++){ cin>>a[i]; } for (i = 0; i < q; i++){ for (j = w; j >= a[i]; j--) b[j] = max(b[j], b[j - a[i]] + a[i]); } cout<<w - b[w]; return 0; }

        • 0
          @ 2022-10-5 9:50:51
          #include <iostream>
          #include <algorithm>
          #include <cmath>
          #include <cstring>
          #include <cstdio>
          #include <string>
          #include <iomanip>
          #include <queue>
          #include <stack>
          #include <list>
          #include <map>
          #include <vector>
          #include <fstream>
          using namespace std;
          const int N = 1e5+10;
          const int INF = 0x3f3f3f3f;
          int maxx = -INF,n,minn = INF,v;
          int a[N];
          void dfs(int step,int sum){
          	if (sum <= v) maxx = max(maxx,sum);
          	if (sum > v or step > n) return;
          	dfs(step+1,sum+a[step]);
          	dfs(step+1,sum);
          }
          int main(){
          	cin >> v >> n;
          	for (int i = 1;i<=n;i++){
          		cin >> a[i];
          	}
          	dfs(1,0);
          	cout << v - maxx;
          	return 0;
          }
          
          • 1

          信息

          ID
          1300
          时间
          1000ms
          内存
          128MiB
          难度
          7
          标签
          递交数
          290
          已通过
          76
          上传者