5 条题解

  • 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;
      }
      
      
      • -1
        @ 2024-12-17 13:47:26
        #include <stdio.h>
        #include <iostream>
        using namespace std;
        inline int read(string n){
        	int x = 0, f = 1;
        	printf("%s", n.c_str());
        	char c = getchar();
        	while(c < '0'  ||  c > '9'){
        		if(c == '-')
        			f = -1;
        		c = getchar();
        	}
        	while(c >= '0'  &&  c <= '9'){
        		x = x * 10 + c - 48;
        		c = getchar();
        	}
        	return x * f;
        }
        inline float input(string n){
        	float x = 0, f = 1, x2 = 0, cnt = 0, i = 0;
        	printf("%s", n.c_str());
        	char c = getchar();
        	while(c < '0'  ||  c > '9'){
        		if(c == '-')
        			f = -1;
        		c = getchar();
        	}
        	while(c >= '0'  &&  c <= '9'){
        		x = x * 10 + c - 48;
        		c = getchar();
        	}
        	c = getchar();
        	while(c >= '0'  &&  c <= '9'){
        		x2 = x2 * 10 + c - 48;
        		cnt++;
        		c = getchar();
        	}
        	for(; i < cnt; i++)
        		x2 /= 10.0;
        	return (x + x2) * f;
        }
        void write(int n) {
            if(n < 0){
                putchar('-');
                n = -n;
            }
            if(n > 9)
        		write(n / 10);
            putchar(n % 10 + '0');
        	return;
        }
        void print(float n){
        	printf("%lf\n", n);
        	return;
        }
        int m, n, f[20010], w[40], i, j;
        int main(){
            m = read("");
            n = read("");
            for(i = 1; i <= n; i++)
                w[i] = read("");
            for(i = 1; i <= n; i++)
                for(j = m; j >= w[i]; j--)
                    if(f[j] < f[j - w[i]] + w[i])
                        f[j] = f[j - w[i]] + w[i];
            write(m-f[m]);
            return 0;
        }
        
        • -1
          @ 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; }

          • -1
            @ 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
            难度
            6
            标签
            递交数
            332
            已通过
            94
            上传者