装箱问题

#include <stdio.h>
#include <string.h>
int max(int a,int b){
    return (a>b?a:b);
}
int main() {
    int v, n;
    scanf("%d %d", &v, &n);
    int w[n+1];
    w[0]=0;
    int dp[n+1][v+1];
    memset(dp, 0, sizeof(dp));
    for (int i=1; i<=n; i++) {
        scanf("%d",&w[i]);
    }
    for (int i=1; i<=n; i++) {
         for (int j=1; j<=v; j++) {
                if(j-w[i]<0){
                    dp[i][j]=dp[i-1][j];
                }
                else {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
                }
         }
    }
     
    printf("%d", v-dp[n][v]);
    
    return 0;
}

package main

import (
    "fmt"
)

func main() {
    var v int
    fmt.Scan(&v)
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&arr[i])
    }
    dp:=make([]int,v+1)
    for _,x:=range arr{
        for i:=v;i>=x;i--{
            dp[i]=max(dp[i],x+dp[i-x])
        }
    }
    fmt.Print(v-dp[v])
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

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

def 省空间解法():
    # f[i][j]表示背包容量为j时，前i个物品能放的最小剩余空间
    f = [V for i in range(V + 1)]
    for i in range(1, n + 1):
        for j in range(V, a[i]-1, -1):  # 注意这边要逆序
            f[j] = min(f[j], f[j - a[i]] - a[i])
    print(f[V])


def 常规解法():
    # f[i][j]表示背包容量为j时，前i个物品能放的最小剩余空间
    f = [[V for i in range(V + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(0, V + 1):
            if j >= a[i]:
                f[i][j] = min(f[i - 1][j], f[i - 1][j - a[i]] - a[i])
            else:
                f[i][j] = f[i - 1][j]
    print(f[n][V])


if __name__ == "__main__":
    V = int(input())
    n = int(input())
    a = [0]
    for i in range(n):
        a.append(int(input()))
    # V, n = 10, 3
    # a = [0, 4, 8, 5]
    # 常规解法()
    省空间解法()

#include<iostream>
using namespace std;
int n,a[32],rest,ans;
void dp(int i){
    if(i==n)return;
    dp(i+1);
    if(rest-a[i]>=0){
        rest-=a[i];
    ans=min(ans,rest);
    dp(i+1);
    rest+=a[i];
    }
}
int main(){
    cin>>rest>>n;
    ans=rest;
    for(int i=0;i<n;i++)
        cin>>a[i];
    dp(0);
    cout<<ans;
    return 0;
}

bigBox = int(input())
n= int(input())
box=[]
for x in range(n):
    box.append(int(input()))
# box.sort()
dp =[0]*(bigBox+2)
dp[0]=1 ##不装
for b in box:  
    j = bigBox
    while j>=b:
        if dp[j]==0:
            dp[j]= dp[j-b]
        j-=1
i=bigBox
while not dp[i]:
    i-=1
print(bigBox-i)