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

<br />

C语言解答

#include<stdio.h>
void main()
{
	int f[20001]={0},o[31],i,j,v,n;
	scanf("%d%d",&v,&n);
	for (i=0;i<n;i++) scanf("%d",&o[i]);
	f[0]=1;
	for (i=0;i<n;i++) 
     	for (j=v;j>=0;j--)
			if (j-o[i]>=0) 
				if (f[j-o[i]]) f[j]=1;
    for (j=v;j>=0;j--) if (f[j]) break;
	printf("%d",v-j);
}

C++解答

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
int V,n,w[35],f[20005];
cin>>V>>n;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++){
for(int j=V;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+w[i]);
}
}
cout<<V-f[V]<<endl;
return 0;
}

Java解答

import java.util.*;

public class Main {
	public static void main(String[] args){
		int v;
		int n;
		int[] a;
		Scanner sc= new Scanner(System.in);
		while(sc.hasNext()){
			v=sc.nextInt();
			n=sc.nextInt();
			a=new int[n];
			for(int i=0;i<n;i++)
				a[i]=sc.nextInt();
			int result=inornot(a,0,v);
			System.out.println(result);
		}
		sc.close();
	}
	public static int inornot(int[] a,int i,int v){
		if(i>=a.length)
			return v;
		else{
			if(a[i]>v){
				return inornot(a,i+1,v);
			}
			else{
				int n=v-a[i];
				int m=inornot(a,i+1,n);
				int k=inornot(a,i+1,v);
				if(m<k)
					return m;     
				else
					return k;
			}
		}
	}
}

Python解答

# coding=utf-8
def main():
    V = int(input())
    n = int(input())
    vv = []
    for _ in range(n):
        vv.append(int(input()))

    dp = [[0 for _ in range(V+1)] for _ in range(n)]
    for i in range(n):
        for j in range(1, V+1):
            if i == 0:
                if j - vv[i] >= 0:
                    dp[i][j] = vv[i]
            else:
                if j - vv[i] >= 0:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - vv[i]] + vv[i])
                else:
                    dp[i][j] = dp[i-1][j]
    print(int(V - dp[n-1][V]))

if __name__ == '__main__':
    main()