【GdufsOJ】购物 - 01背包

Description

双十一仅剩3天了，小明决定准备剁手了。请你告诉小明，买哪些商品可以让小明剩下的钱最少。

Input

第一行包括数字n和m，代表采购清单上有n件商品，小明有m元钱。 0<=n<=100, 0<=m<=1000。 接下来n行，每行包含2个数字，表示商品名称和价格

Output

按照采购清单中商品的顺序，输出小明购买哪些商品。每个商品一行。

Sample Input

4 750
Laptop 3500
Bag 400
Shoes 100
Watch 300

Sample Output

Bag
Watch

#include <iostream>
#include <stack>
using namespace std;
int n, m;
int w[105], vis[105];
int dp[1005][1005];
char name[105][1005];
stack <int> s;
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i)
cin >> name[i] >> w[i];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(j<w[i])
dp[i][j] = dp[i][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+w[i]);
}
}
int M = m;
for(int i = n; i > 1; --i){
if(dp[i][M]!=dp[i-1][M]){
s.push(i);
M -= w[i];
}
}
if(dp[1][M])s.push(1);
cout << m-dp[n][m] << endl;
while(!s.empty()){
cout << name[s.top()]<<endl;
s.pop();
}
return 0;
} 

最后

以上就是文静冰棍为你收集整理的【GdufsOJ】购物 - 01背包的全部内容，希望文章能够帮你解决【GdufsOJ】购物 - 01背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。