# 1113. 装箱问题

while True:
try:
V = int(input())
n = int(input())
items = [int(i) for i in input().split()]
res = [0]*(V+1)
for i in range(n):
for j in range(V, items[i]-1, -1):
res[j] = max(res[j], res[j-items[i]]+items[i])
print(V-res[V])
input()  # 数据集里有蜜汁空行
except:
break


DP

//状态:dp[i][j] 代表将前i个物品放入背包为j大小的最大值
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int a[32];
int dp[32][20010];

int main() {
int v, n;
while (cin >> v >> n) {
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= v; ++j) {
if (j >= a[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
int ans = v - dp[n][v];
cout << ans << endl;
}
return 0;
}


dfs+剪枝

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int a[N];
int n, v;
int _max;
void DFS(int index, int sum) {
if (sum > v) {
return;
}
if (index == n) {
if (sum <= v && sum > _max) {
_max = sum;
}
return;
}
DFS(index + 1, sum);
DFS(index + 1, sum + a[index]);
}

int main() {
while (cin >> v >> n) {
fill(a, a + N, 0);
_max = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
DFS(0, 0);
int ans = v - _max;
cout << ans << endl;
}
return 0;
}


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int a[maxn];
int Max = 0;        //最大的体积;
int V,n;

void dfs(int index,int sum) {   //index:当前选的下标，weight当前总重量
if(sum > V || index > n) return;
if(sum > Max) Max = sum;
dfs(index+1,sum);       //不选当前
dfs(index+1,sum+a[index]);  ///选当前
}

int main() {
while(cin>>V>>n) {
Max = 0;
memset(a,0,sizeof(a));
for(int i = 0;i < n;i++) cin>>a[i];
dfs(0,0);//当前体积
cout<<V-Max<<endl;
}
return 0;
}


#include <iostream>
#include <vector>
using namespace std;

int main() {
unsigned v, n;
while (scanf("%u%u", &v, &n) ^ EOF) {
unsigned vol[30];
for (unsigned i = 0; i < n; ++i)
scanf("%u", vol + i);
vector<unsigned> dp(20001, 0);
for (unsigned i = 0; i < n; ++i)
for (unsigned j = v; j >= vol[i]; --j)
if (j >= vol[i] && dp[j] < dp[j - vol[i]] + vol[i])
dp[j] = dp[j - vol[i]] + vol[i];
printf("%u\n", v - dp[v]);
}
}