題目描述

有一個箱子容量為v(正整數(shù)，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積? (正整數(shù))。要求從? n? 個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。?

輸入格式

第一行，一個整數(shù)，表示箱子容量；? 第二行，一個整數(shù)，表示有n個物品；? 接下來n行，分別表示這n個物品的各自體積。?

輸出格式

一個整數(shù)，表示箱子剩余空間。

樣例輸入

24
6
8
3
12
7
9
7

樣例輸出

0

解題思路

這一題乍一看與背包問題相似，但是相較于背包問題更加簡單，沒有價值設定，一開始我試著用更加通俗易懂的方法寫，即從大到小依次遍歷，進行裝箱，直到裝不下為止

我用了兩個for循環(huán)以求left（剩余空間大小），即

//第一個for循環(huán)遍歷到 裝入下一個箱子，空間為負為止
for(int i=0;i<n;i++)//將箱子從大到小依次裝到箱中{if(arr[i]+sum<v){sum+=arr[i];}}left=v-sum;//這里空間剩余：3
for(int i=0;i<n;i++)
{if(arr[i]<=left)//以剩余空間作為判斷條件    {         sum+=arr[i];left=v-sum;//更新left}
}

最終代碼得?

#include<stdio.h>int main()
{int v, n;//v表示體積，n表示物品個數(shù)int max, temp,sum=0,left;scanf("%d", &v);scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++){scanf("%d", &arr[i]);}for (int i = 0; i < n; i++)//冒泡排序,將體積從大到小放入arr[i]中{for(int j=0;j < n-1-i;j++){if (arr[j + 1] > arr[j]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
/*for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
*/for(int i=0;i<n;i++)//將箱子從大到小依次裝到箱中{if(arr[i]+sum<v){sum+=arr[i];}}left=v-sum;//這里空間剩余：3for(int i=0;i<n;i++){if(arr[i]<=left)//以剩余空間作為判斷條件sum+=arr[i];left=v-sum;}printf("%d",left);return 0;
}

但這樣寫不具有通用性，還是要用到動態(tài)規(guī)劃算法，代碼如下

其中最重要的一段即

 for(i=1;i<=n;i++)
//從1開始是因為當v=0, 箱子裝不下任何東西，i=0表示第0件物品，即沒有物品，所以跳過 for(j=v;j>=1;j--)
/*
把數(shù)組壓縮到一維必須逆序，因為01背包問題就是由舊值推新值，從前面開始的話，舊值就會過早被新值覆蓋 
例如：
如果a[30]在a[20]的基礎上加了w[i]=10，表示30容量這個背包它拿了w[i]=10這個東西了，但是--它沒有考慮：a[20]里面是否拿過w[i]=10這個東西，所以要j--;
也就是說箱子的體積從小到大遍歷，物品從大到小開始裝，這樣才能避免重復裝入物品
*/{//j可以看作箱子當前的容量 if(w[i]<=j)//判斷是否能裝下物品i a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式為a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) }

for(j=v;j>=1;j--)

還是不懂為什么j--

那么就多寫：

for(j=v;j>=1;j--)的情況

?for(j=1;j<=v;j++)的情況

?可以看到從a[14]開始，舊值已經(jīng)覆蓋新值了

注：a[j]為沒放入，a[j-w[i]]+w[i]為放入
如下圖所示a[j]為V(容量)，a[j-w[i]]為放入w[i]后剩余的容量，a[j-w[i]]+w[i]為放入w[i]后的容量大小，不理解的可以依據(jù)上圖觀察規(guī)律：

最終代碼如下?

#include<stdio.h>int w[40]={0};//注意初始化 ,這里表示物品的體積
int a[30011]={0};//這里表示v
int MAX(int n,int m)
{if(m<=n) return n;else return m;
}
int main()
{int n,i,j,v;scanf("%d",&v); scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&w[i]);for(i=1;i<=n;i++)//從1開始是因為當v=0, 箱子裝不下任何東西，i=0表示第0件物品，即沒有物品，所以跳過 for(j=v;j>=1;j--)
/*
把數(shù)組壓縮到一維必須逆序，因為01背包問題就是由舊值推新值，從前面開始的話，舊值就會過早被新值覆蓋 
例如：
如果a[30]在a[20]的基礎上加了w[i]=10，表示30容量這個背包它拿了w[i]=10這個東西了，但是--它沒有考慮：a[20]里面是否拿過w[i]=10這個東西，所以要j--;
也就是說箱子的體積從小到大遍歷，物品從大到小開始裝，這樣才能避免重復裝入物品
*/{//j可以看作箱子當前的容量 if(w[i]<=j)//判斷是否能裝下物品i a[j]=MAX(a[j],a[j-w[i]]+w[i]);//原式為a[i][j]=MAX(a[i-1][j],a[i-1][j-w[i]]+w[i]) }// a[j]為不拿，a[j-w[i]]+w[i]為拿//a[j-w[i]]+w[i]意為放入物品i后，總占用空間=物品i所占的空間+箱子剩余的空間 j-w[i] 所能被占用的最大空間 a[j-w[i]]printf("%d",v-a[v]);//此時的a[v]表示當容量為v時，箱子已被占用空間a[v] return 0;
}

這是@佳佳佳佳佳博主的圖，有助于理解?

MAX(a[i-1][j],a[i-1][j-w[i]]+w[i])?

這是最簡單的背包問題，一定要理解，如果還有點迷糊的話，可以看看這篇文章

http://t.csdn.cn/X7GLD

或者

http://t.csdn.cn/CleVM