0/1背包问题
描述
有n个重量和价值分别为wi和vi的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最小值
题解
-
dp[i][j]
表示从第i
个物品开始挑选总重小于j的物品时得到的最大价值
显然,可以得到如下的递推表达式:
int solve(){
for(int i=n-1;i>=0;i--){
for(int j=w[i];j<W;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[1]);
}
}
return dp[0][W];
}
-
dp[i+1][j]
表示从第1到第i个物品中开始挑选总重小于j的物品时得到的最大价值
显然,可以得到下面的递推表达式
int solve(){
for(int i=0;i<n;i++){
for(int j=0;j<W;j++){
///该判断不能省略
if(j<v[i]){
dp[i+1][j]=dp[i][j];
}
else
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[1]);
}
}
return dp[n][W];///注意是dp[n][W] 而不是dp[n-1][W]
}
- 看网上大佬的题解,还有下面这种,
dp[]
只有一维,在数据量非常大的时候,一维数据结构才能解题。
递推表达式为:
int solve(){
for(int i=0;i<n;i++){
for(int j=W;j>=w[i];j--){
/**
j从W到w[i],每个物品只对dp[]产生一次影响,这种循环方式具有序列性
*/
dp[j]=max(dp[j],dp[j-w[i]+v[i])
}
return dp[W];
}
/**
错误示例
for(int i=0;i<n;i++){
for(int j=w[i];j<W;j++){
//每一个物品对dp[]产生累计作用,被多次使用了
dp[j]=max(dp[j],dp[j-w[i]+v[i])
}
}
*/
}
例题
-
代码
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define maxn 1000
using namespace std;
int n,a[maxn],dp[maxn][maxn];
int m;
int main()
{
while(scanf("%d",&n)==1&&n){
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
if(m<5){
printf("%d\n",m);
continue;
}
sort(a,a+n);
memset(dp,0,sizeof(dp));
m-=5;
///错误示例
/**
for(int i=0;i<n-1;i++){
for(int j=a[i];j=m;j++){
dp[j]=max(dp[j],dp[j-a[i]]+a[i])
}
}
*/
///1)正确代码
for(int i=n-2;i>=0;i--){
for(int j=a[i];j<=m;j++){
///这里无需判断j>=a[i],因为dp[0][m]的取值不会受到判断条件的影响
dp[i][j]=max(dp[i+1][j],dp[i+1][j-a[i]]+a[i]);
}
}
printf("%d\n",m+5-dp[0][m]-a[n-1]);
}
///2)正确代码
/**
for(int i=0;i<n-1;i++){
for(int j=0;j<=m;j++){
///这里需要j>=a[i]判断,如果省略这一步,后面的dp[n-1][m]很有可能取不到值
if(j>=a[i]){
dp[i+1][j]=max(dp[i][j],dp[i][j-a[i]]+a[i]);
}
else
dp[i+1][j]=dp[i][j];
}
}
printf("%d\n",m+5-dp[n-1][m]-a[n-1]);
*/
///3)正确代码 一维的dp[]
/**
for(int i=0;i<n-1;i++){
for(int j=m;j>=a[i];j--){
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
}
printf("%d\n",m+5-dp[m]-a[n-1]);
*/
return 0;
}