题意:
输入第一行为n,x两个正整数。分别表示n本书和可以包邮的价格下限x。随后n行表示第i本书的价格。
现在要求出在所有大于x的价格中,最小的那个。这里的价格是指任意买m( m <= n)本书的总价格。
思路:
动态规划,0-1背包问题。
0-1背包问题是说:有n件物品,每件物品重量为w[i],其价值为v[i],现在有个容量为m的背包,如何选择物品使得装入背包的价值总量最大?
这里如何转化为0-1背包问题呢?可以定义:(假设所有数组存储下标从1开始)
sum = w[1] + w[2] + …… + w[n];
m = sum - x;
(背包最大容量)
dp
二维数组:
1)初始化:
dp[i][0] = 0 ( 0 <= i <= n); dp[0][j] = 0 (0 <= j <= m)
2)状态转移方程:
if ( j < w [ i ] ) dp[ i ] [ j ] = dp[ i-1 ] [ j ]
else dp[ i ] [ j ] = max ( dp[ i-1 ] [ j ], dp[ i-1 ] [ j - w [ i ] ] + w [ i ] )
最后返回
sum - dp[n][m];
时间复杂度为
O(nm)
#include <iostream>
#define maxn 300010
using namespace std;
int dp[31][maxn]={0};
int main(){
int n,x,sum=0,m;
cin>>n>>x;
int *A = (int*)malloc(sizeof(int)*(n+1));
for(int i = 1; i <= n; i ++){
cin>>A[i];
sum+=A[i];
m = sum - x;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
if(j < A[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]]+A[i]);
cout<<sum - dp[n][m]<<endl;
return 0;